Partition Equal Subset Sum

Beginne mit der Gesamtsumme. Ist sie ungerade, gibt es keine Aufteilung, denn zwei gleiche ganze Zahlen ergeben zusammen eine gerade Zahl. Andernfalls muss jede Gruppe genau target = total / 2 ergeben. Sobald du Werte findest, die target ergeben, bilden die nicht ausgewählten Werte von selbst die andere Hälfte. Es genügt also, eine Frage zu beantworten: Gibt es eine Teilmenge, deren Summe target ergibt?

Gehe die Werte der Reihe nach durch und triff für jeden eine Entscheidung: Lege ihn in die erste Gruppe oder lasse ihn für die zweite. Eine Hilfsfunktion reach(i, remaining) gibt an, ob die Werte ab Index i zusammen remaining ergeben können. Sie gibt true zurück, wenn remaining 0 erreicht, false, wenn keine Werte mehr übrig sind oder der Wert unter 0 fällt, und versucht andernfalls beide Möglichkeiten für nums[i].

Jede Teilmenge entspricht einem Entscheidungspfad. Daher kann die Suche keine Aufteilung übersehen, und die Antwort ist korrekt. Sie ist langsam, weil es 2^n Pfade gibt und eine Eingabe ohne mögliche Aufteilung sie dazu zwingt, fast alle davon auszuprobieren. Nimm 199 Kopien von 100 und eine 98: Die Gesamtsumme ist 19998, das Ziel 9999 wird nie erreicht, und die Suche probiert jede Möglichkeit aus, höchstens 99 der Hunderter auszuwählen – etwa 4 × 10^59 Pfade. Schon 40 Werte ergeben 2^40, also etwa 10^12 Pfade.

Die Rekursion stellt immer wieder dieselbe Frage. reach(i, remaining) hängt nur von zwei Zahlen ab: i von 0 bis n und remaining von 0 bis target. Dadurch gibt es höchstens (n+1) × (target+1) verschiedene Fragen, an den Grenzen etwa 201 × 10001 ≈ 2 × 10^6 – wenige genug, um jede einzelne davon einmal zu beantworten.

Erstelle die Antworten in einer Tabelle von vorne nach hinten. can[i][s] gibt an, ob sich mit einigen der ersten i Werte die Summe s bilden lässt. Ohne Werte ist nur die Summe 0 möglich, daher ist Zeile 0 überall false außer bei can[0][0]. Für den Wert num = nums[i-1] gibt es zwei Möglichkeiten, s zu erreichen: num nicht verwenden, sodass die vorherigen Werte bereits s ergeben, oder ihn verwenden, sodass die vorherigen Werte s-num ergeben. Das ist die ganze Regel: can[i][s] = can[i-1][s] or can[i-1][s-num], wobei der zweite Teil nur zählt, wenn s ≥ num. Jede Zeile liest nur die darüberliegende Zeile, daher wird jeder Wert höchstens einmal verwendet.

Bei [6, 1, 4, 9, 2] mit dem Zielwert 11 wachsen die erreichbaren Summen von {0} auf {0, 6}, dann auf {0, 1, 6, 7} und anschließend auf {0, 1, 4, 5, 6, 7, 10, 11}. Die Summe 11 erscheint nach der 4 (6 + 1 + 4), und die folgenden Zeilen behalten sie bei. Die Antwort ist can[n][target]. Jede Zelle erfordert konstanten Aufwand, daher betragen Zeit- und Speicherbedarf jeweils O(n × target).

Jede Zeile der Tabelle liest nur die Zeile darüber. Daher reicht eine Zeile aus, wenn du sie direkt aktualisierst: reach[s] gibt an, ob sich einige der bisher gesehenen Werte zu s summieren. Die Gefahr liegt in der Reihenfolge der Aktualisierungen. Wenn du s aufsteigend durchläufst, wurde reach[s-num] möglicherweise bereits durch dieselbe Zahl num aktiviert. Bei [3, 9] und dem Zielwert 6 setzt die 3 reach[3] auf wahr und liest diesen Wert anschließend, um reach[6] zu aktivieren, als hättest du zwei Dreien, und du gibst für eine nicht existierende Aufteilung „wahr“ zurück.

Durchlaufe s absteigend, von target bis num. Dann ist s-num ein kleinerer Index, den dieser Wert noch nicht verändert hat, sodass reach[s-num] weiterhin das Ergebnis von vor dem Hinzukommen von num enthält. Das entspricht genau can[i-1][s-num] aus der Tabelle, und die einzelne Zeile übernimmt die Arbeit der gesamten Tabelle.

Du kannst auch sofort aufhören, sobald reach[target] wahr wird, denn spätere Werte fügen nur erreichbare Summen hinzu und entfernen niemals eine. Im schlimmsten Fall sind es weiterhin O(n × target) Schritte, etwa 2 × 10^6, und der Speicherbedarf sinkt auf target + 1 boolesche Werte.