Teilmengensumme und Partitionierung
Erreichen Sie ein Ziel mit einer ausgewählten Teilmenge
Teilmengensumme und Partitionierung ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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.
Die Teilmengensummenfrage
Gegeben sind Zahlen und ein Zielwert. Kann eine Teilmenge genau diesen Zielwert ergeben? Das ist ein Rucksackproblem, bei dem der Wert dem Gewicht entspricht.
Boolesche DP statt Werte
Hier verfolgen Sie die Erreichbarkeit, nicht ein Maximum. Sei dp[s] genau dann True, wenn eine Teilmenge die Summe s ergibt.
dp = [False] * (target + 1)
dp[0] = TrueNull ist immer erreichbar
Die leere Teilmenge hat die Summe null, daher beginnt dp[0] mit True. Jede andere Summe beginnt mit False, bis eine Zahl ihre Erreichbarkeit nachweist.
Der Übergang
Markieren Sie für jede Zahl s als erreichbar, wenn s - num bereits erreichbar war. Eine Zahl kann viele Summen auf True setzen.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Wieder rückwärts
Jede Zahl darf höchstens einmal verwendet werden, daher läuft die innere Schleife rückwärts, genau wie beim 0/1-Rucksackproblem. Vorwärts würde eine Zahl erneut verwenden.
Das Ergebnis ablesen
Nach der Verarbeitung aller Zahlen beantwortet dp[target] die Frage. True bedeutet, dass eine gültige Teilmenge existiert; False bedeutet, dass dies unmöglich ist.
Das Partitionsproblem kennenlernen
Beim Partitionsproblem lautet die Frage: Können Sie das Array in zwei Hälften mit gleicher Summe aufteilen? Es lässt sich direkt auf die Teilmengensumme zurückführen.
Die Gesamtsumme halbieren
Ist die Gesamtsumme ungerade, sind gleich große Hälften unmöglich, und Sie können sofort Nein antworten. Andernfalls lautet das Ziel einfach total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Die Teilmengensumme wiederverwenden
Prüfen Sie nun einfach, ob eine Teilmenge total // 2 erreicht. Wenn eine Hälfte das Ziel erreicht, bildet der Rest automatisch die passende zweite Hälfte.
Die Komplexität
Die Kosten liegen in der Größenordnung von n mal Zielwert, also bei einer pseudo-polynomialen Schranke. Das ist schnell, wenn das Ziel klein ist, und langsam, wenn die Summen sehr groß sind.
Eine Problemfamilie
Teilmengensumme, Partition und das 0/1-Rucksackproblem verwenden denselben Kern. Erkennen Sie das Nehmen-oder-Liegenlassen-Muster, können Sie dieselbe Schleife wiederverwenden.
Schnelltest
Testen Sie die Reduktion auf Partition.
Zusammenfassung
Sie haben die Teilmengensumme mit boolescher DP und einer rückwärts laufenden Schleife gelöst und anschließend Partition darauf reduziert, die Gesamtsumme // 2 zu erreichen. Derselbe Kern, neue Erfolge. ✅
Häufig gestellte Fragen
Ist die Lektion „Teilmengensumme und Partitionierung“ kostenlos?
Ja — der vollständige Text von „Teilmengensumme und Partitionierung“ 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 „Teilmengensumme und Partitionierung“?
Erreichen Sie ein Ziel mit einer ausgewählten Teilmenge 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 4 von 4.
Wie lange dauert die Lektion „Teilmengensumme und Partitionierung“?
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
- 0/1-Knapsack: Nehmen oder ablehnen
- Knapsack mit optimiertem Speicherbedarf
- Unbeschränktes Knapsack und Münzwechsel-DP
- Teilmengensumme und Partitionierung