Subset Sum Problem
nums enthält positive ganze Zahlen, und target ist eine positive ganze Zahl. Kannst du einige der Werte auswählen, wobei jede Position höchstens einmal gewählt werden darf, sodass ihre Summe genau target ergibt? Gib true zurück, wenn das möglich ist, und false, wenn keine Auswahl funktioniert.
Funktion
- numsinteger-array
- die positiven Werte, aus denen du auswählen kannst
- targetinteger
- die genaue Summe, die die ausgewählten Werte erreichen müssen
- Gibt zurückboolean
- true, wenn einige der Werte zusammen genau target ergeben, andernfalls false
Einschränkungen
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Beispiele
- Eingabe
- nums = [8, 3, 11, 5, 7]target = 15
- Ausgabe
- true
- Erklärung
- 8 + 7 = 15, also lautet die Antwort
true. Die Auswahl 3 + 5 + 7 funktioniert ebenfalls; eine Auswahl genügt.
- Eingabe
- nums = [6, 9, 12, 15]target = 20
- Ausgabe
- false
- Erklärung
- Jeder Wert ist ein Vielfaches von 3, daher ist auch jede Summe dieser Werte ein Vielfaches von 3. 20 ist es nicht, also lautet die Antwort
false.
- Eingabe
- nums = [4, 1, 2]target = 8
- Ausgabe
- false
- Erklärung
- Alle drei Werte zusammen ergeben 4 + 1 + 2 = 7, was kleiner als 8 ist. Daher kann keine Auswahl diesen Wert erreichen, und die Antwort ist
false.
Weiterführende Frage
Zwei gleiche Werte an verschiedenen Positionen zählen als unterschiedliche Auswahlen. Wie viele Auswahlen ergeben target?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Beginne mit
nums[0]. Wenn deine Auswahl diesen Wert enthält, müssen die anderen Wertetarget-nums[0]ergeben. Andernfalls müssen sietargetergeben. Beides ist dieselbe Frage für ein kürzeres Array.Ob die Werte ab Position
ieine Summerergeben können, hängt nur voniundrab, undrwird nie größer alstarget. Es gibt also höchstens etwa 200 × 10^4 verschiedene Fragen, und jede davon kann einmal beantwortet werden.Verwende einen booleschen Wert pro Summe von 0 bis
target, wobei zunächst nur die Summe 0 erreichbar ist. Füge die Werte nacheinander hinzu: Eine Summeswird erreichbar, wenns-numbereits erreichbar war. Aktualisiere die Summen von oben nach unten, damit ein Wert nicht zweimal verwendet wird, und lies die Antwort beitargetab.
Lösung
Für jeden Wert gibt es bei einer Auswahl ein Ja oder Nein, daher ergeben 200 Werte 2^200 Auswahlmöglichkeiten. Allerdings zählen nur Summen bis target ≤ 10^4. Erfasse, welche Summen sich mit den bisherigen Werten bilden lassen: Jeder neue Wert verschiebt diese Erfassung um seine Größe, und die Suche wird zu einer Tabelle aus n × target Wahrheitswerten.
Nimm jeden Wert oder überspringe ihn
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
canMake(i, remaining) prüft, ob sich mit den Werten ab Position i genau remaining bilden lässt. Nimm nums[i], wenn es passt; dann bleibt remaining-nums[i] für den Rest übrig. Falls das nicht funktioniert, überspringe es. Jede Auswahl ist ein Pfad, daher findet die Suche eine Auswahl, wenn eine existiert.
Wenn es keine gibt, durchläuft die Suche alle Möglichkeiten. Bei 200 Vielfachen von 3, die jeweils höchstens 300 betragen, und einem Zielwert von 9998 funktioniert keine Auswahl, doch beliebige 33 Werte bleiben unter dem Zielwert: über 10^37 Pfade.
Algorithmus
- Schreibe
canMake(i, remaining). - Ein
remainingvon 0 bedeutet, dass die Auswahl vollständig ist: Gib true zurück. Wenn keine Werte mehr übrig sind und noch etwas gebildet werden muss, gib false zurück. - Wenn
nums[i] ≤ remaininggilt undcanMake(i+1, remaining-nums[i])true ist, gib true zurück. - Andernfalls gib
canMake(i+1, remaining)zurück. - Gib
canMake(0, target)zurück.
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)Fülle eine Tabelle der erreichbaren Summen aus
Idee
Die Rekursion hängt nur von einer Position und einer verbleibenden Summe zwischen 0 und target ab, und viele Pfade erreichen dasselbe Paar. Fülle stattdessen eine Tabelle. made[i][s] ist wahr, wenn eine Auswahl aus den ersten i Werten genau die Summe s ergibt; die leere Auswahl ergibt 0. Mit num = nums[i-1] wird die Summe s erreicht, wenn sie ohne num erreicht wurde, also made[i-1][s], oder wenn num s-num vervollständigt, also made[i-1][s-num], wobei s ≥ num gilt.
Im ersten Beispiel sind nach der 8 die erreichten Summen 0 und 8. Die 3 fügt 3 und 11 hinzu, die 11 nur 14, die 5 fügt 5 und 13 hinzu, und 8 + 7 ergibt 15. Bei den Grenzwerten hat die Tabelle 201 × 10001 Zellen, also etwa 2 × 10^6 Schritte.
Algorithmus
- Initialisiere
madeals Array mit n+1 Zeilen und target+1 booleschen Werten, die alle false sind. Setzemade[0][0]für die leere Auswahl auf true. - Zeile
iverarbeitet den Wertnum = nums[i-1]füri= 1 bis n. - Setze für jede Summe
svon 0 bistargetmade[i][s]aufmade[i-1][s]. - Wenn
s ≥ numgilt undmade[i-1][s-num]true ist, setzemade[i][s]auf true. - Gib
made[n][target]zurück.
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# leave num out, or put it in on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]Eine Zeile mit Summen, von oben aktualisiert
Idee
Jede Zeile liest nur die Zeile davor, daher kann ein Array made[s] sie speichern. Überschreibst du von unten nach oben, fließt ein Wert in sich selbst ein: Mit nums = [5] und dem Zielwert 10 wird s = 5 wahr, dann liest s = 10 diesen frisch eingetragenen Wert und verwendet die 5 zweimal.
Gehe stattdessen von target abwärts bis num. Der Lesezugriff auf s-num trifft auf eine Zelle mit niedrigerem Index, die der Durchlauf noch nicht überschrieben hat. Daher sieht er die Zeile von vor num. Eine erreichbare Summe bleibt erreichbar, sodass du sofort aufhören kannst, sobald made[target] wahr ist. Der Speicherbedarf sinkt auf target + 1 boolesche Werte.
Algorithmus
- Beginne mit einem einzelnen Array aus
target + 1booleschen Werten, in dem nurmade[0]den Wert true hat. - Nimm die Werte der Reihe nach. Lasse für jede
numden Wert vonsabsteigend vontargetbisnumlaufen. - Markiere
made[s], wennmade[s-num]den Wert true hat. - Gib sofort
truezurück, sobaldmade[target]markiert ist. - Wenn zuvor alle Werte aufgebraucht sind, lautet die Antwort
false.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
Stolperfallen und Grenzfälle
- Eine aufsteigende Schleife über die Summen verwendet einen Wert zweimal:
[3]mit Ziel 9 ergibt true. made[0] = truevergessen. Jede Summe baut auf der leeren Auswahl auf, daher ist jede Antwort false.- Zuerst die größten Werte auswählen. Bei
[6, 5, 5]mit Ziel 10 bleiben bei einer Auswahl von 6 noch 4 übrig, die sich nicht bilden lassen, während 5 + 5 = 10 ergibt. - Ein Wert über
target, wie in[10000]mit Ziel 1, darf nichts ändern. Swift'snum...targetstoppt das Programm und R's(num+1):(target+1)zählt rückwärts, also prüfe zuerstnum ≤ target. - In Lua und R liegt der Eintrag für die Summe
sam Indexs + 1.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität des Teilmengensummenproblems?
Die Tabelle benötigt O(n × target) Zeit, etwa 2 × 10^6 Schritte für 200 Werte und einen Zielwert von 10^4, und eine Zeile reduziert den Speicherbedarf auf O(target). Der Aufwand hängt von der numerischen Größe des Zielwerts ab, daher ist die Methode pseudo-polynomiell und für einen Zielwert wie 10^18 nutzlos. Im Allgemeinen ist das Teilmengensummenproblem NP-vollständig.
Wie hängt Subset Sum mit Partition Equal Subset Sum und dem 0/1-Rucksackproblem zusammen?
Partition Equal Subset Sum ist Subset Sum mit target = total / 2, nachdem geprüft wurde, ob die Gesamtsumme gerade ist. Subset Sum ist ein 0/1-Rucksackproblem, bei dem jeder Wert sein eigenes Gewicht ist und der Rucksack exakt gefüllt werden muss, sodass die Tabelle boolesche Werte statt Optimalwerte enthält.
Funktioniert die Teilmengensumme mit negativen Zahlen?
Die Idee funktioniert, der obige Code nicht. Bei negativen Zahlen reichen die erreichbaren Summen von der Summe der negativen Zahlen bis zur Summe der positiven Zahlen. Verschiebe daher jeden Index um diese niedrigste Summe und fülle die Zeile auf dieselbe Weise. Ein Wert, der größer als die verbleibende Summe ist, kann nicht mehr übersprungen werden.
Wie findest du heraus, welche Werte das Ziel ergeben?
Behalte die vollständige Tabelle bei und beginne bei made[n][target]. Gehe eine Zeile nach der anderen nach oben: Wenn made[i-1][s] wahr ist, wurde nums[i-1] nicht benötigt; andernfalls notiere es und ziehe es von s ab. Du hörst bei Summe 0 mit einer gültigen Auswahl auf.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def isSubsetSum(nums, target):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
nums = [8, 3, 11, 5, 7] target = 15
Erwartete Ausgabe
true