Partition Equal Subset Sum

Gegeben sei ein nichtleeres Array positiver Ganzzahlen nums. Bestimmen Sie, ob Sie es in zwei Teilmengen mit gleicher Summe aufteilen können. Beispielsweise kann [1, 5, 11, 5] in [1, 5, 5] und [11] aufgeteilt werden; beide Summen betragen 11. Wenn die Gesamtsumme ungerade ist, lautet die Antwort sofort False. Andernfalls müssen wir eine Teilmenge finden, deren Summe total_sum // 2 beträgt — ein klassisches Subset-Sum-Problem.

Die entscheidende Reduktion: Wenn die Gesamtsumme S gerade ist und eine Teilmenge die Summe S//2 ergibt, summieren sich die verbleibenden Elemente automatisch ebenfalls zu S//2. Daher reduziert sich Partition Equal Subset Sum auf die Frage: Ergibt die Summe irgendeiner Teilmenge von nums S//2? Dies ist das klassische NP-vollständige Problem Subset Sum, das wir mit 0/1-Rucksack-DP in einer Laufzeit von O(n × S) lösen.

Definieren Sie ein boolesches Array dp[c], wobei dp[c] = True bedeutet, dass eine Teilmenge mit genau der Summe c existiert. Initialisieren Sie dp[0] = True (die leere Teilmenge hat die Summe 0) und alle anderen Werte mit False. Iterieren Sie für jede Zahl num die Kapazität von target abwärts bis num (Rückwärtsiteration beim 0/1-Rucksackproblem) und setzen Sie dp[c] = dp[c] or dp[c - num].

Für [1, 5, 11, 5] gilt: total=22 und target=11. Zu Beginn ist dp[0]=True. Nach num=1: dp[1]=True. Nach num=5: dp[5]=True, dp[6]=True. Nach num=11: dp[11]=True (unter Verwendung der einzelnen 11). Wir haben bereits dp[11]=True gefunden, verarbeiten aber weiterhin alle Zahlen. Endergebnis: dp[11]=True, daher ist eine Aufteilung möglich.

Wir können einen vorzeitigen Abbruch einbauen: Sobald dp[target] den Wert True annimmt, geben wir sofort True zurück. Das kann die Best-Case-Szenarien erheblich beschleunigen. Wenn außerdem ein einzelnes Element target entspricht, können wir ebenfalls sofort True zurückgeben. Ist ein einzelnes Element größer als target, kann es nicht in einer Teilmenge enthalten sein, deren Summe target ergibt; die übrigen Elemente müssen wir jedoch weiterhin prüfen.

Eine Alternative besteht darin, eine Menge erreichbarer Summen zu verwalten. Beginnen Sie mit {0}. Fügen Sie für jede Zahl zu jeder Summe der aktuellen Menge die Zahl hinzu: reachable = reachable | {s + num for s in reachable}. Filtern Sie anschließend alle Summen heraus, die target überschreiten. Prüfen Sie am Ende, ob target in der Menge enthalten ist. Dieser Ansatz ist intuitiv, kann aber mehr Speicher benötigen und in der Praxis langsamer sein.

Der DP-Ansatz benötigt eine Laufzeit von O(n × S), wobei S = sum(nums) gilt, und verwendet O(S) Speicherplatz für das boolesche Array. Für die Einschränkungen bei LeetCode (n ≤ 200, sum ≤ 20.000) sind das höchstens 4.000.000 Operationen – sehr schnell. Der Mengenansatz hat dieselbe asymptotische Komplexität, kann in der Praxis aber aufgrund des Aufwands für die Mengenerstellung langsamer sein.

Ein verwandtes Problem besteht darin, die Anzahl der Teilmengen zu zählen, deren Summe einem Zielwert entspricht. Ändern Sie den DP von booleschen Werten zu Ganzzahlen: dp[c] = number of ways to reach sum c. Verwenden Sie statt OR eine Addition: dp[c] += dp[c - num]. Initialisieren Sie dp[0] = 1. Die Rückwärtsiteration bleibt unverändert. Diese Verallgemeinerung zeigt, wie sich das Rucksack-Template an unterschiedliche Fragen zu Teilmengen anpassen lässt.

Rechnen Sie mit folgenden Rückfragen: (1) Was ist, wenn Sie die tatsächliche Aufteilung zurückgeben müssen? – Dafür ist ein 2D-DP zur Rekonstruktion erforderlich. (2) Was ist, wenn Elemente negativ sein können? – Verschieben Sie das Ziel oder verwenden Sie statt eines Arrays ein Dictionary. (3) Wie hoch ist die Zeitkomplexität? – O(n × sum). (4) Können Sie die Lösung verbessern, wenn viele Zahlen gleich sind? – Ja, verwenden Sie eine Häufigkeitszählung, um die Anzahl der äußeren Iterationen zu reduzieren. Erwähnen Sie diese Abwägungen stets proaktiv.

Partition Equal Subset Sum ist eine direkte Anwendung des 0/1-Rucksackproblems: Die Elemente sind die Zahlen, die Gewichte entsprechen den Werten und die Rucksackkapazität entspricht target. Wir prüfen, ob der maximale Wert target entspricht (Machbarkeit), und nicht, wie hoch der maximale Wert ist. Die Rückwärtsiteration ist identisch; lediglich die Operation ändert sich von max zu einem booleschen or. Diese Verbindung in einem Vorstellungsgespräch zu erkennen, zeigt ein ausgeprägtes Erkennen von Mustern.

Folgende Sonderfälle müssen Sie berücksichtigen: (1) Array der Länge 1 – ein einzelnes Element kann nicht aufgeteilt werden, daher immer False; (2) alle Elemente identisch und ihre Anzahl gerade – das Ergebnis hängt von den einzelnen Werten ab; (3) sehr große Summen – prüfen Sie die Einschränkungen, bevor Sie das DP-Array anlegen; (4) Elemente, die größer als target sind – sie können übersprungen werden, da sie niemals Teil einer Teilmenge mit der Summe target sein können. Die Prüfung des größten Elements als vorzeitiger Abbruch behandelt Fall (4) effizient.

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.

In dieser Lektion haben Sie gelernt: Partition Equal Subset Sum reduziert sich auf Subset Sum mit target = total//2, der eindimensionale boolesche DP dp[c] verwendet dieselbe Rückwärtsiteration wie das 0/1-Rucksackproblem und der Ansatz lässt sich auf das Zählen von Teilmengen verallgemeinern, indem boolesches OR durch eine Ganzzahladdition ersetzt wird. Als Nächstes behandeln wir Target Sum und wandeln die Vorzeichenbelegung in ein Rucksackproblem über Teilmengensummendifferenzen um.