Combination Sum

Eine Kombination wird vollständig dadurch beschrieben, wie viele Exemplare jedes Kandidaten sie verwendet. Für [6, 2, 3] und das Ziel 8 besteht die Antwort [2, 3, 3] aus einer 2, zwei 3ern und keiner 6. Eine Möglichkeit, alle Antworten zu finden, besteht also darin, jede mögliche Anzahl für jeden Kandidaten auszuprobieren und die Auswahlmöglichkeiten zu behalten, deren Summe genau target ergibt. Ein Kandidat c passt höchstens target / c Mal, seine Anzahl reicht also von 0 bis zu dieser Grenze.

Stell dir einen Entscheidungsbaum mit einer Ebene pro Kandidat vor, nachdem sie sortiert wurden. Auf Ebene i entscheidest du, wie viele Exemplare des i-ten Werts du nimmst, und jedes Blatt ganz unten steht für eine vollständige Auswahl von Anzahlen. Jedes Multiset hat genau eine Liste von Anzahlen, sodass keine Kombination zweimal gefunden wird. Wenn du zuerst die größte Anzahl ausprobierst, ergibt sich auch die erforderliche Reihenfolge: Wenn sich zwei Antworten erstmals bei der Anzahl eines bestimmten Werts unterscheiden, enthält diejenige mit mehr Exemplaren diesen kleinen Wert noch, während die andere bereits einen größeren enthält, und kommt daher zuerst.

Das Problem ist die Größe des Baums. Die Anzahl der Blätter ist das Produkt von target / c + 1 über alle Kandidaten: Für das sortierte [2, 3, 6] und das Ziel 8 sind das 5 × 3 × 2 = 30 Blätter für 3 Antworten. Jeder Kandidat, der größer als target / 2 ist, verdoppelt die Anzahl der Blätter, obwohl er höchstens einmal passt. 40 solcher Kandidaten allein ergeben also 2^40, also etwa 10^12, Blätter. Die großen Tests sind so aufgebaut, und dieser Ansatz kann sie nicht rechtzeitig abschließen.

Baue jede Kombination Wert für Wert auf, so, wie du sie aufschreiben würdest: in aufsteigender Reihenfolge. Der Startindex erzwingt diese Reihenfolge. Nachdem du nums[i] platziert hast, darf der nächste Wert wieder nums[i] sein, weil ein Kandidat mehrfach vorkommen kann, oder ein beliebiger späterer Wert, aber niemals ein früherer. Daher durchläuft der Aufruf, der den Index i platziert hat, nur die Indizes ab i. Jede Kombination hat genau eine aufsteigende Reihenfolge und somit genau einen Pfad im Baum. Ein Duplikat wie [3, 2, 3] wird also nie erstellt.

Hier ist der gesamte Baum für die sortierte Folge [2, 3, 6] und das Ziel 8. An der Wurzel sind noch 8 übrig; sie probiert 2, 3 und 6 aus. Unter 2 sind noch 6 übrig. Unter 2, 2 sind noch 4 übrig, und bei 2, 2, 2 bleiben noch 2, die durch eine weitere 2 zur Lösung [2, 2, 2, 2] werden; bei 2, 2, 3 bleibt noch 1 übrig, und der Pfad endet erfolglos. Unter 2, 3 sind noch 3 übrig, und es dürfen nur 3 und 6 ausprobiert werden; die 3 ergibt [2, 3, 3]. Unter 2, 6 bleibt nichts übrig: [2, 6]. Unter 3 dürfen nur 3 und 6 ausprobiert werden, und bei 3, 3 bleiben noch 2 übrig, die keine der beiden Zahlen auffüllt. Unter 6 sind noch 2 übrig, und es darf nur 6 ausprobiert werden. Insgesamt zwölf Aufrufe, verglichen mit den 30 Blättern des ersten Ansatzes.

Durch Sortieren wird aus einer Sackgasse ein vorzeitiger Abbruch. Wenn nums[i] größer ist als der verbleibende Rest, ist auch jeder spätere Wert größer. Deshalb verlässt du die Schleife mit break, statt den Rest zu testen. Im obigen Baum betrachtet der Knoten 2, 2, 3 mit einem Rest von 1 die 3, stellt fest, dass sie nicht passt, und betrachtet die 6 gar nicht mehr. Die Suche besucht nur Präfixe, deren Summe höchstens target ist. Deshalb benötigen die großen Tests, die den ersten Ansatz ausbremsen, hier nur einige tausend Aufrufe.

Die Ausgabereihenfolge ergibt sich aus demselben Durchlauf. Auf jeder Ebene probiert die Schleife zuerst kleinere Werte aus, und jede Kombination wird in aufsteigender Reihenfolge geschrieben. Zwei Antworten unterscheiden sich erstmals auf der Ebene, auf der sich ihre Pfade verzweigen. Da der Pfad mit dem kleineren Wert dort zuerst erkundet wird, erscheinen die Antworten in lexikografischer Reihenfolge. Eine Kombination kann niemals das Präfix einer anderen sein, weil die Werte positiv sind und beide dieselbe Summe erreichen.