Zielsumme mit positiven und negativen Vorzeichen

Gegeben seien ein ganzzahliges Array nums und eine ganze Zahl target. Weisen Sie jeder Zahl ein Vorzeichen + oder - zu, sodass der resultierende Ausdruck den Wert target ergibt. Geben Sie die Anzahl der unterschiedlichen Möglichkeiten zurück. Für nums=[1,1,1,1,1] und target=3 gibt es beispielsweise 5 Möglichkeiten: Sie wählen 4 Elemente an unterschiedlichen Positionen für das positive und 1 Element für das negative Vorzeichen.

Ein DFS-Ansatz weist jeder Zahl entweder + oder - zu und ruft sich rekursiv auf. Dabei wird die Anzahl der Blattknoten zurückgegeben, die target erreichen. Das ist korrekt, hat aber eine Zeitkomplexität von O(2^n) und ist damit exponentiell. Für n=20 sind das mehr als eine Million rekursive Aufrufe. Im Vorstellungsgespräch ist es sinnvoll, zuerst den DFS-Ansatz zu erwähnen und dann schnell zur DP-Optimierung überzugehen.

Erweitern Sie die DFS um Memoisierung: Der Zustand ist (index, current_sum). Da current_sum von -total bis +total reichen kann, gibt es O(n × total) eindeutige Zustände. Mit Memoisierung benötigt die DFS O(n × total) Zeit und Speicherplatz. Dieser Ansatz funktioniert und ist in Vorstellungsgesprächen gültig, aber die DP auf Basis der Transformation ist eleganter und speichereffizienter.

Sei P die Menge der Zahlen mit dem Vorzeichen + und N die Menge der Zahlen mit dem Vorzeichen -. Dann gilt: sum(P) - sum(N) = target und sum(P) + sum(N) = total. Durch Addieren ergibt sich: 2 × sum(P) = target + total, also sum(P) = (target + total) / 2. Das Problem reduziert sich auf: Zählen Sie die Teilmengen von nums, deren Summe (target + total) / 2 ergibt. Dies ist genau die Variante des 0/1-Rucksackproblems, bei der Teilmengen gezählt werden.

Prüfen Sie vor der Ausführung des DP: (1) target + total muss gerade sein (andernfalls ist sum(P) keine ganze Zahl und das Problem ist unlösbar); (2) abs(target) > total bedeutet, dass target selbst dann nicht erreichbar ist, wenn alle Vorzeichen gleich sind. Wenn eine der Prüfungen fehlschlägt, geben Sie sofort 0 zurück. Diese Prüfungen behandeln Sonderfälle sauber, ohne Sonderlogik innerhalb der DP-Schleife zu benötigen.

Für nums=[1,1,1,1,1] und target=3 gilt: total=5, new_target=(3+5)//2=4. Wir zählen die Teilmengen mit der Summe 4 aus [1,1,1,1,1]. Das ist C(5,4)=5 (wählen Sie 4 Einsen für das positive Vorzeichen, die fünfte erhält das negative Vorzeichen: 1+1+1+1-1=3). Der DP gibt korrekt 5 zurück. Die Transformation bildet das Problem der Vorzeichenbelegung elegant auf ein standardmäßiges Problem zum Zählen von Teilmengen ab.

Wenn nums Nullen enthält, ändert die Zuweisung von + oder - zu einer Null die Summe nicht. Jede Null verdoppelt die Anzahl der gültigen Belegungen. Der DP behandelt dies automatisch: Bei der Verarbeitung von num=0 läuft die innere Schleife range(new_target, -1, -1) von new_target abwärts bis 0, und dp[c] += dp[c - 0] = dp[c] verdoppelt alle erreichbaren Summen. Bei Verwendung von range(new_target, num-1, -1), die bei num=0 von new_target abwärts bis 0 läuft, ist keine Sonderbehandlung erforderlich.

Die Brute-Force-DFS hat eine Komplexität von O(2^n). Die memoiserte DFS benötigt O(n × total) Zeit und O(n × total) Speicherplatz. Der eindimensionale DP auf Basis der Transformation benötigt O(n × new_target) Zeit und O(new_target) Speicherplatz, wobei new_target ≤ total gilt. Der eindimensionale DP benötigt deutlich weniger Speicher als die Memoisierung, weil durch die Transformation die Indexdimension entfällt.

Target Sum verbindet mehrere Konzepte aus Rucksackproblemen: Es beginnt als Belegungsproblem, wird in ein Teilmengensummenproblem umgewandelt (wie Partition Equal Subset Sum) und verwendet dasselbe Template des 0/1-Rucksackproblems mit Rückwärtsiteration, diesmal jedoch mit Zählung (wie bei Coin Change II). Wenn Sie diese Verbindungen beherrschen, können Sie neue Probleme in Vorstellungsgesprächen anhand ihrer strukturellen Ähnlichkeit mit bekannten Mustern schnell einordnen.

Wichtige Fälle: (1) target = total: genau eine Möglichkeit (alle Vorzeichen positiv); (2) target = -total: genau eine Möglichkeit (alle Vorzeichen negativ); (3) target = 0 bei ausschließlich Nullen: Das Ergebnis ist 2^n; (4) sehr großes total bei kleinem n – die Größe des eindimensionalen DP-Arrays ist durch total/2 begrenzt. Erklären Sie im Vorstellungsgespräch die Transformation vor dem Programmieren mündlich – sie ist die nicht offensichtliche entscheidende Erkenntnis, die starke Kandidaten auszeichnet.

Ohne die Transformation definieren wir dp[i][s] als die Anzahl der Möglichkeiten, den ersten i Zahlen Vorzeichen zuzuweisen und die Summe s zu erreichen. Da die Summe negativ sein kann, verschieben wir sie um total: Verwenden Sie dp[i][s + total]. Dafür ist eine 2D-Tabelle der Größe (n+1) × (2*total+1) erforderlich. Der Ansatz ist zwar korrekt, benötigt aber mehr Speicher und lässt sich unter dem Zeitdruck eines Vorstellungsgesprächs schwieriger schnell programmieren als der eindimensionale Rucksack-DP nach der Transformation.

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

In dieser Lektion haben Sie gelernt: Target Sum wandelt die Vorzeichenbelegung in das Zählen von Teilmengen mit der Summe (target + total) / 2 um, der eindimensionale 0/1-Rucksack-DP zählt Teilmengen in O(n × new_target) Zeit und mit O(new_target) Speicherplatz durch Rückwärtsiteration und frühe Gültigkeitsprüfungen (ungerade Summe, |target| > total) verhindern eine unnötige Ausführung des DP. Als Nächstes wechseln wir mit Dijkstras Algorithmus und einer Prioritätswarteschlange zu Problemen über kürzeste Wege.