Combination Sum

Q: Wie hoch ist die Zeitkomplexität von Combination Sum?

Die Backtracking-Suche ist exponentiell. Bei n Kandidaten, dem Zielwert t und dem kleinsten Kandidaten m enthält eine Kombination höchstens t/m Werte mit jeweils höchstens n Auswahlmöglichkeiten: O(n^(t/m)) . Der zusätzliche Speicherbedarf beträgt O(t/m) für den Pfad und den Aufrufstapel, zuzüglich der Ausgabe.

Q: Warum rekursierst du bei Combination Sum mit i und nicht mit i + 1?

Mit Rekursion mit i kann der nächste Wert erneut derselbe Kandidat sein. So wird ein Wert mehr als einmal verwendet. Rekursion mit i + 1 geht zum nächsten Kandidaten weiter, sodass jeder Kandidat höchstens einmal verwendet werden kann.

Q: Kann Combination Sum mit dynamischer Programmierung gelöst werden?

Ja. Halte für jede Summe von 0 bis target die Kombinationen fest, mit denen sie erreicht wird, und füge jeweils einen Kandidaten hinzu, damit jede Liste aufsteigend bleibt. Es erkundet keine Sackgasse zweimal, speichert aber jede unvollständige Kombination für jede Summe, was wesentlich mehr Speicher kostet. Da die Ausgabe selbst exponentiell groß sein kann, ist Backtracking die übliche Lösung.

MittelBacktracking

+10

Du erhältst eine Liste candidates mit verschiedenen positiven ganzen Zahlen und eine positive ganze Zahl target. Finde jede Kombination von Kandidaten, deren Summe genau target ergibt, wobei du jeden Kandidaten beliebig oft verwenden kannst. [2, 3, 3] und [3, 2, 3] sind dieselbe Kombination.

Gib jede Kombination in aufsteigender Reihenfolge und die Kombinationen in lexikografischer Reihenfolge zurück: An der ersten Position, an der sich zwei Kombinationen unterscheiden, kommt diejenige mit dem kleineren Wert zuerst.

Funktion

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: die verschiedenen Werte, die du in beliebiger Reihenfolge und beliebig oft verwenden kannst
targetinteger: Die Gesamtsumme jeder Kombination muss genau erreichen
Gibt zurückinteger-2d-array: jede Kombination, deren Summe dem Zielwert entspricht, jeweils aufsteigend sortiert und lexikografisch geordnet

Einschränkungen

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Alle Werte in candidates sind unterschiedlich und haben keine bestimmte Reihenfolge.
Mindestens eine Kombination erreicht target, und höchstens 150 tun das.

Beispiele

Eingabe: candidates = [6, 2, 3]target = 8
Ausgabe: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Erklärung: Vier 2en, 2 + 3 + 3 und 2 + 6 ergeben alle 8, geordnet nach ihrem zweiten Wert. Ohne eine 2 bleiben nur 3en und 6en übrig, und ihre Summen sind Vielfache von 3, was bei 8 nicht der Fall ist.

Eingabe: candidates = [5, 3, 4]target = 11
Ausgabe: [[3, 3, 5], [3, 4, 4]]
Erklärung: 3 + 3 + 5 und 3 + 4 + 4 ergeben beide 11, und [3, 3, 5] kommt zuerst, weil sein zweiter Wert, 3, kleiner als 4 ist. Keine Kombination, die nur aus 4ern und 5ern besteht, ergibt 11.

Weiterführende Frage

Jeder Kandidat darf nun höchstens einmal verwendet werden, und candidates kann wiederholte Werte enthalten. Wie änderst du die Suche, damit keine Kombination doppelt vorkommt?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Falle besteht darin, dieselbe Kombination zweimal zu bilden: 2, 3, 3 und 3, 2, 3 sind eine Antwort. Bilde jede Kombination in aufsteigender Reihenfolge, sodass es genau einen Pfad gibt, und sortiere die Kandidaten, damit ein Zweig endet, sobald der nächste Wert größer ist als der verbleibende Wert.

Probiere jede Anzahl für jeden Kandidaten aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Eine Kombination wird vollständig dadurch beschrieben, wie viele Exemplare jedes Kandidaten sie verwendet: [2, 3, 3] ist eine 2, zwei 3en und keine 6. Pro sortiertem Kandidaten werden alle Anzahlen von target / c bis hinunter zu 0 ausprobiert; behalten werden die Auswahlmöglichkeiten, deren Summe genau target ergibt. Jede Kombination hat genau eine Liste von Anzahlen, sodass keine zweimal gefunden wird. Größere Anzahlen zuerst ergeben lexikografische Reihenfolge: Wenn sich zwei Antworten zum ersten Mal unterscheiden, enthält diejenige mit mehr Exemplaren eines Werts diesen Wert weiterhin, während die andere einen größeren Wert enthält.

Für [2, 3, 6] und das Ziel 8 gibt es 5 × 3 × 2 = 30 Blätter für 3 Antworten. Jeder Kandidat über target / 2 verdoppelt die Anzahl der Blätter, sodass 40 solcher Kandidaten 2^40, also etwa 10^12, ergeben.

Algorithmus

Sortiere die Kandidaten und behalte pro Wert eine Anzahl bei.
Versuche in choose(i, total) jeden Zähler k von target / nums[i] absteigend bis 0 und rufe choose(i + 1, total + k × nums[i]) auf.
Sobald für jeden Wert eine Anzahl feststeht, behalte die Kombination, wenn total gleich target ist, und gib sie anhand der Anzahlen aus.
Rufe choose(0, 0) auf.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

In aufsteigender Reihenfolge zurückverfolgen und beschneiden

Idee

Nachdem du nums[i] platziert hast, kann der nächste Wert wieder nums[i] oder ein späterer Wert sein, aber niemals ein früherer. Eine Kombination hat genau eine aufsteigende Reihenfolge und daher genau einen Pfad; [3, 2, 3] wird nie erstellt.

Für das sortierte [2, 3, 6] und das Ziel 8 erreichen die Pfade 2, 2, 2, 2 und 2, 3, 3 sowie 2, 6 den Wert 8. Beim Pfad 2, 2, 3 bleibt 1 übrig, und die Suche wird beendet, ohne 6 zu prüfen; bei 3, 3 bleiben 2 übrig, wozu kein Wert passt. Das sind 12 Aufrufe gegenüber den 30 Blättern beim Zählen.

Auf jeder Ebene probiert die Schleife zuerst die kleineren Werte aus, sodass die Antworten in lexikografischer Reihenfolge eintreffen. Keine Antwort ist ein Präfix einer anderen, da die Werte positiv sind und beide dieselbe Summe erreichen.

Algorithmus

Sortiere die Kandidaten.
Speichere in backtrack(start, remaining) eine Kopie des gemeinsamen path, wenn remaining 0 ist.
Durchlaufe andernfalls i ab start. Wenn nums[i] > remaining, break: Jeder spätere Wert ist größer.
Füge nums[i] hinzu, rufe backtrack(i, remaining - nums[i]) auf und entferne es dann wieder.
Rufe backtrack(0, target) auf und gib die gespeicherten Kombinationen zurück.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Stolperfallen und Grenzfälle

Auf jeder Ebene alle Kandidaten durchlaufen, statt ab dem aktuellen Index. [2, 3, 3], [3, 2, 3] und [3, 3, 2] ergeben dann drei Antworten.
Mit i + 1 statt mit i rekursiv aufrufen. Jeder Wert kann dann nur einmal vorkommen, sodass [2, 2, 2, 2] fehlt.
path selbst statt einer Kopie speichern. Jede gespeicherte Antwort ist dann dieselbe Liste, die durch Backtracking am Ende geleert wurde.
break bei Kandidaten verwenden, die du nicht sortiert hast. Bei [6, 2, 3] und dem Restwert 2 wird die Schleife bei 6 beendet und versucht die 2 nie.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Combination Sum?

Die Backtracking-Suche ist exponentiell. Bei n Kandidaten, dem Zielwert t und dem kleinsten Kandidaten m enthält eine Kombination höchstens t/m Werte mit jeweils höchstens n Auswahlmöglichkeiten: O(n^(t/m)). Der zusätzliche Speicherbedarf beträgt O(t/m) für den Pfad und den Aufrufstapel, zuzüglich der Ausgabe.

Warum rekursierst du bei Combination Sum mit i und nicht mit i + 1?

Mit Rekursion mit i kann der nächste Wert erneut derselbe Kandidat sein. So wird ein Wert mehr als einmal verwendet. Rekursion mit i + 1 geht zum nächsten Kandidaten weiter, sodass jeder Kandidat höchstens einmal verwendet werden kann.

Kann Combination Sum mit dynamischer Programmierung gelöst werden?

Ja. Halte für jede Summe von 0 bis target die Kombinationen fest, mit denen sie erreicht wird, und füge jeweils einen Kandidaten hinzu, damit jede Liste aufsteigend bleibt. Es erkundet keine Sackgasse zweimal, speichert aber jede unvollständige Kombination für jede Summe, was wesentlich mehr Speicher kostet. Da die Ausgabe selbst exponentiell groß sein kann, ist Backtracking die übliche Lösung.

def combinationSum(candidates, target):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

candidates = [6, 2, 3]
target = 8

Erwartete Ausgabe

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]