Teilmengen und Potenzmenge
Erzeugen Sie mithilfe von Backtracking und Bitmaskierung alle Teilmengen einer Menge und behandeln Sie Duplikate, indem Sie sortieren und wiederholte Elemente überspringen.
Teilmengen und Potenzmenge ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Teilmengen und die Potenzmenge
Die Potenzmenge einer Menge S ist die Sammlung aller möglichen Teilmengen von S, einschließlich der leeren Menge und S selbst. Eine Menge mit n Elementen hat genau 2ⁿ Teilmengen. Für [1, 2, 3] lauten die 8 Teilmengen: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Dies ist ein grundlegendes kombinatorisches Problem, das in Interviewfragen zum Finden aller möglichen Kombinationen, Partitionen oder Auswahlmöglichkeiten vorkommt.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Teilmengen mit Backtracking erzeugen
Verwenden Sie die Vorlage zum Auswählen, Erkunden und Rückgängigmachen. Die entscheidende Designentscheidung besteht darin, bei jedem rekursiven Aufruf den aktuellen unvollständigen Pfad sofort (vor der Auswahl weiterer Elemente) zu den Ergebnissen hinzuzufügen. So wird jeder Zustand — leer, teilweise oder vollständig — als gültige Teilmenge erfasst. Erhöhen Sie den Index start, damit nur Elemente rechts vom zuletzt ausgewählten Element berücksichtigt werden. Dadurch vermeiden Sie Duplikate und bewahren die Reihenfolge.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Bitmaskierung
Eine Alternative zu Backtracking ist die Bitmaskierung: Jede Teilmenge entspricht einer n-Bit-Zahl, bei der ein Bit i mit dem Wert 1 bedeutet, dass das Element i enthalten ist. Durchlaufen Sie die Zahlen von 0 bis 2ⁿ - 1 und extrahieren Sie für jede Zahl die Bits, um die Teilmenge zu bilden. Dieser Ansatz ist iterativ, in der Praxis oft schneller und sehr einfach zu programmieren. Er lässt sich jedoch nicht so gut auf Probleme mit Einschränkungen (z. B. einer Summenbegrenzung) verallgemeinern.
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differIterative Erzeugung von Teilmengen
Der iterative Ansatz baut die Potenzmenge Element für Element auf. Beginnen Sie mit [[] ] (der leeren Menge). Für jedes neue Element duplizieren Sie alle vorhandenen Teilmengen und fügen das neue Element an jede duplizierte Teilmenge an. Nach der Verarbeitung von n Elementen enthält das Ergebnis alle 2ⁿ Teilmengen. Dies entspricht der Bitmaskierung, ist aber für Personen, die mit bitweisen Operationen nicht vertraut sind, besser lesbar.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Subsets II: Umgang mit Duplikaten
Wenn die Eingabe Duplikate enthält, erzeugt der naive Ansatz doppelte Teilmengen. Bei [1, 2, 2] würden beide Vorkommen von 2 unabhängig voneinander [1, 2] erzeugen. Die Lösung: Sortieren Sie zuerst das Array und überspringen Sie einen Kandidaten auf der aktuellen Ebene, wenn er dem vorherigen Kandidaten auf derselben Ebene entspricht. Konkret lautet die Schleife: if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsetsWarum das Überspringen von Duplikaten funktioniert
Die Bedingung i > start and nums[i] == nums[i-1] überspringt ein Duplikat nur auf derselben Rekursionsebene (mit demselben start). Sie verhindert nicht, dass derselbe Wert auf unterschiedlichen Tiefen ausgewählt wird. Für [1, 2, 2] fügen wir auf Ebene 0 die erste 2 (Index 1) ein und fügen dann auf der nächsten Ebene (start=2) die zweite 2 hinzu, um [2, 2] zu bilden. Wenn wir jedoch auf Ebene 0 erneut die zweite 2 einfügen wollten, erkennt die Bedingung dies und überspringt sie.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6Teilmengen fester Größe (k-Kombinationen)
Wenn nur Teilmengen mit genau der Größe k erzeugt werden sollen (LeetCode 77: Combinations), kommt eine vorzeitige Abbruchbedingung hinzu: Wenn die verbleibenden Elemente den Pfad nicht auf die Größe k auffüllen können, wird dieser Zweig verworfen. Die Bedingung zum Verwerfen lautet i > n - (k - len(path)): Wenn nicht genügend Elemente übrig sind, wird vorzeitig abgebrochen. Dadurch wird der Suchraum im Vergleich zum Erzeugen aller Teilmengen und anschließenden Filtern erheblich verkleinert.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120Anwendungen der Potenzmenge
Das Muster der Potenzmenge kommt in vielen Varianten von Interviewaufgaben vor: (1) Aufteilen in zwei gleich große Teilmengen — prüfen, ob die Summe einer Teilmenge total/2 ergibt. (2) Maximales XOR zweier Teilmengen — alle Teilmengenpaare ausprobieren. (3) Minimale Kosten für die Auswahl von k Elementen — k-Teilmengen aufzählen. Obwohl direktes Aufzählen exponentiell ist, lassen sich viele dieser Aufgaben mit DP lösen, sobald Sie die Struktur erkannt haben. Die Darstellung als Potenzmenge hilft Ihnen, den Zustandsraum zu identifizieren, selbst wenn Sie den Ansatz anschließend optimieren.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20Prüfen einer Teilmengensumme
Bei Subset Sum lautet die Frage: Ergibt die Summe irgendeiner Teilmenge des Arrays einen Zielwert? Dies lässt sich mit Backtracking (exponentiell) oder DP (polynomiell) lösen. Die Backtracking-Variante ist unkompliziert, wird für große Eingaben jedoch unpraktikabel. Die DP-Variante (boolesche Tabelle dp[target+1]) ist in Interviews der bevorzugte Ansatz. Wenn Sie beide verstehen, können Sie den Kompromiss gut erklären: Backtracking liefert alle Lösungen, während DP das Entscheidungsproblem effizient beantwortet.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # TrueKomplexität der Teilmengenerzeugung
Das Erzeugen aller Teilmengen hat unvermeidbar eine Zeitkomplexität von O(n × 2ⁿ) — es gibt 2ⁿ Teilmengen mit einer durchschnittlichen Größe von n/2. Wenn alle Teilmengen verlangt werden, kann kein Algorithmus dies besser lösen. Bei Aufgaben, die eine einzelne Teilmenge mit einer bestimmten Eigenschaft suchen (z. B. die maximale Summe), sollten Sie DP oder einen Greedy-Ansatz bevorzugen. Wichtige Erkenntnis für Interviews: Fragen Sie immer, ob Sie alle Teilmengen aufzählen müssen oder nur feststellen sollen, ob irgendeine Teilmenge eine Bedingung erfüllt — davon hängt ab, ob eine exponentielle oder polynomielle Laufzeit akzeptabel ist.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')Vergleich aller drei Ansätze
Zum Erzeugen aller Teilmengen gilt: Backtracking ist am vielseitigsten — es lässt sich leicht an Duplikate und zusätzliche Bedingungen anpassen. Bitmaskierung ist kompakt und schnell, aber auf n ≤ 30 beschränkt (aufgrund der Ganzzahlgröße). Der iterative Ansatz ist intuitiv und vermeidet den zusätzlichen Aufwand der Rekursion. Alle drei erzeugen eine Ausgabe mit O(n × 2ⁿ). In einem Interview zeigt Backtracking, dass Sie den rekursiven Entscheidungsprozess verstanden haben, der sich auf schwierigere Aufgaben übertragen lässt. Erwähnen Sie bei der Diskussion der Ansätze alle drei Varianten.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Backtracking erzeugt alle Teilmengen, indem jeder bisherige Pfad vor der weiteren Erkundung zu den Ergebnissen hinzugefügt wird, Duplikate werden durch Sortieren und das Überspringen wiederholter Werte auf derselben Rekursionstiefe mit der Bedingung i > start and nums[i] == nums[i-1] behandelt und Bitmaskierung bietet eine kompakte iterative Alternative, bei der jede Teilmenge einer eindeutigen Bitmaske entspricht. Als Nächstes behandeln wir Permutationen und Kombinationen — verwandte Aufzählungsprobleme mit anderen Bedingungen.
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „Teilmengen und Potenzmenge“ kostenlos?
Ja — der vollständige Text von „Teilmengen und Potenzmenge“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Teilmengen und Potenzmenge“?
Erzeugen Sie mithilfe von Backtracking und Bitmaskierung alle Teilmengen einer Menge und behandeln Sie Duplikate, indem Sie sortieren und wiederholte Elemente überspringen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Teilmengen und Potenzmenge“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Backtracking-Schema: Auswählen, Erkunden, Auswahl zurücknehmen
- Teilmengen und Potenzmenge
- Permutationen und Kombinationen
- N-Damen und Constraint Propagation