Kleine Implementierung: Teilmengensumme

Klassisches Teilproblem: gibt es eine Teilmenge mit gegebener Summe? Entscheide pro Element: nehmen oder weglassen.

Partition mit gleicher Summe: Partition Equal Subset Sum [1].

$$\sum_i x_i a_i = t,\quad x_i\in\{0,1\}$$

Wo gebraucht

Knapsack-Verwandte, Target-Sum in Pipelines, Lehrbrücke zu DP: erst vollständige Suche, dann Memoization derselben Zustände.

Vertiefung

Bei der Teilmengensumme entscheidet die Rekursion für jedes Element zwischen Aufnehmen und Überspringen. Ein kompakter Zustand besteht aus Index und noch benötigter Summe. Zwei verschiedene Auswahlpfade können dasselbe Zustandspaar erreichen, weshalb Memoisierung viele Wiederholungen beseitigt.

Bei ausschliesslich nichtnegativen Zahlen darf ein negativer Rest als erfolglos gelten. Mit negativen Eingaben wäre dieser Schnitt unsicher, weil spätere Werte den Rest wieder ausgleichen könnten. Die Korrektheit einer Optimierung hängt somit von den zugesicherten Eingabeeigenschaften ab.

Schwierigkeitsstufen

1. Die beiden rekursiven Fälle für eine kleine Liste ausführen.
2. Sichere Abbruchbedingungen aus dem Wertebereich ableiten.
3. Index und Restsumme als Memoisierungsschlüssel verwenden.

Fallstricke

Wer nur nach der Restsumme memoisiert, vermischt Zustände mit unterschiedlichen noch verfügbaren Elementen. Ausserdem muss der leere Teilmengenkandidat für Zielsumme null bewusst behandelt werden.