Alle Teilmengen erzeugen
Wählen Sie jedes Element aus oder überspringen Sie es
Alle Teilmengen erzeugen ist eine kostenlose Coding 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum Teilmengen erzeugen
Bei vielen Aufgaben in Programmierwettbewerben sollen Sie jede Teilmenge einer kleinen Menge ausprobieren. Mit Rekursion können Sie alle Teilmengen übersichtlich und zuverlässig auflisten. 🧩
Jedes Element auswählen oder überspringen
Die Grundidee: Für jedes Element treffen Sie eine binäre Entscheidung – Sie nehmen es auf oder lassen es weg. Jede vollständige Folge von Entscheidungen ergibt eine Teilmenge.
Wie viele Teilmengen gibt es
Eine Menge mit n Elementen hat genau 2 hoch n Teilmengen, weil jedes Element die Anzahl verdoppelt. Halten Sie n daher klein, etwa bei 20 oder weniger.
Der rekursive Plan
Führen Sie einen Index durch das Array. Verzweigen Sie an jedem Index zweimal: einmal, indem Sie das Element nehmen, und einmal, indem Sie es überspringen.
Der Basisfall
Wenn der Index über das letzte Element hinausgeht, ist der aktuelle Pfad eine vollständige Teilmenge. Dieser Moment ist Ihr Basisfall, in dem Sie sie speichern.
Teilmengenrekursion im Code
Dieser rekursive Durchlauf speichert am Ende eine Teilmenge und untersucht anschließend ab jedem Index die beiden Möglichkeiten: überspringen oder nehmen.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Durch Rückgängigmachen zurückgehen
Wenn Sie ein Element anhängen, entfernen Sie es nach der Rekursion wieder, damit der nächste Zweig mit einem sauberen Zustand beginnt. Dieser Rückgängigmachungsschritt ist das Herzstück des Backtrackings.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()Die Bitmasken-Alternative
Sie können auch jede ganze Zahl von 0 bis 2 hoch n minus 1 einer Teilmenge zuordnen, wobei jedes Bit ein aufgenommenes Element markiert.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Vor dem Speichern eine Kopie anlegen
Speichern Sie immer eine Kopie der aktuellen Liste, nicht die Liste selbst. Andernfalls überschreiben spätere Änderungen jede gespeicherte Teilmenge. ⚠️
Kombinationen erzeugen
Um Teilmengen einer festen Größe k zu erhalten, beenden Sie den Zweig, sobald die ausgewählte Anzahl k erreicht. So werden aus Teilmengen Kombinationen.
Wo Teilmengen vorkommen
Die Aufzählung von Teilmengen löst kleine Rucksackprobleme, Aufgaben zur Teamauswahl und Machbarkeitsprüfungen, bei denen Sie jede mögliche Auswahl testen müssen.
Kurze Überprüfung
Wie viele Teilmengen hat eine Menge mit n Elementen?
Zusammenfassung: Bei jedem Element verzweigen
Sie haben gelernt, alle Teilmengen aufzulisten, indem Sie jedes Element auswählen oder überspringen und nach jedem Zweig die Änderung rückgängig machen. Halten Sie n klein, da die Anzahl 2 hoch n beträgt. 🎯
Häufig gestellte Fragen
Ist die Lektion „Alle Teilmengen erzeugen“ kostenlos?
Ja — der vollständige Text von „Alle Teilmengen erzeugen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Alle Teilmengen erzeugen“?
Wählen Sie jedes Element aus oder überspringen Sie es Du übst Coding 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding 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 „Alle Teilmengen erzeugen“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding 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
- Rekursiv denken: Basisfall und Rekursion
- Alle Teilmengen erzeugen
- Permutationen und die N-Queens-Idee
- Mit Beschneiden das Zeitlimit einhalten