Kombinationssumme II

40. Kombinationssumme II

Schwierigkeit:Mittel

Themen:Array, Backtracking

Suchen Sie anhand einer Sammlung von Kandidatennummern (Kandidaten) und einer Zielnummer (Ziel) alle eindeutigen Kombinationen in Kandidaten, bei denen die Summe der Kandidatennummern das Ziel ergibt.

Jede Zahl in Kandidaten darf nur einmal in der Kombination verwendet werden.

Hinweis: Der Lösungssatz darf keine doppelten Kombinationen enthalten.

Beispiel 1:

• Eingabe: Kandidaten = [10,1,2,7,6,1,5], Ziel = 8
• Ausgabe: [[1,1,6], [1,2,5], [1,7], [2,6]]

Beispiel 2:

• Eingabe: Kandidaten = [2,5,2,1,2], Ziel = 5
• Ausgabe: [[1,2,2], [5]]

Einschränkungen:

• 1 <= Candidates.length <= 100
• 1 <= Kandidaten[i] <= 50
• 1 <= Ziel <= 30

Lösung:

Wir können einen Backtracking-Ansatz verwenden. Die Schlüsselidee besteht darin, das Array zunächst zu sortieren, um Duplikate einfacher zu verarbeiten, und dann alle möglichen Kombinationen mithilfe von Backtracking zu untersuchen.

Lassen Sie uns diese Lösung in PHP implementieren: 40. Kombinationssumme II

Erläuterung:

1. Sortierung: Das Kandidaten-Array ist sortiert, um Duplikate einfacher zu handhaben und sicherzustellen, dass Kombinationen in einer sortierten Reihenfolge gebildet werden.
2. Backtracking: Die Backtrack-Funktion wird verwendet, um alle möglichen Kombinationen zu erkunden.
   • Wenn das Ziel Null wird, addieren wir die aktuelle Kombination zum Ergebnis.
   • Wir iterieren ausgehend vom aktuellen Index über die Kandidaten. Wenn ein Kandidat derselbe ist wie der vorherige, überspringen wir ihn, um doppelte Kombinationen zu vermeiden.
   • Wir subtrahieren den aktuellen Kandidaten vom Ziel und rufen rekursiv die Backtrack-Funktion mit dem neuen Ziel und dem nächsten Index auf.
   • Der rekursive Aufruf wird fortgesetzt, bis wir entweder eine gültige Kombination finden oder alle Möglichkeiten ausschöpfen.
3. Beschneiden: Wenn der Kandidat das Ziel überschreitet, brechen wir frühzeitig aus der Schleife aus, da auch weitere Kandidaten das Ziel übertreffen werden.

Dieser Code gibt alle eindeutigen Kombinationen aus, die in der Summe das Ziel ergeben, und stellt gleichzeitig sicher, dass jeder Kandidat in jeder Kombination nur einmal verwendet wird.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonKombinationssumme II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!