Subset Sum Problem
nums contiene numeri interi positivi e target è un numero intero positivo. Riesci a scegliere alcuni dei valori, al massimo una volta per posizione, in modo che la loro somma sia esattamente target? Restituisci true se ci riesci e false se nessuna scelta funziona.
Funzione
- numsinteger-array
- i valori positivi tra cui puoi scegliere
- targetinteger
- la somma esatta che i valori selezionati devono raggiungere
- Restituisceboolean
- true quando alcuni dei valori sommati danno esattamente target, false altrimenti
Vincoli
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Esempi
- Input
- nums = [8, 3, 11, 5, 7]target = 15
- Output
- true
- Spiegazione
- 8 + 7 = 15, quindi la risposta è
true. Anche la scelta 3 + 5 + 7 funziona; basta una scelta.
- Input
- nums = [6, 9, 12, 15]target = 20
- Output
- false
- Spiegazione
- Ogni valore è un multiplo di 3, quindi anche ogni loro somma è un multiplo di 3. 20 non lo è, quindi la risposta è
false.
- Input
- nums = [4, 1, 2]target = 8
- Output
- false
- Spiegazione
- Tutti e tre i valori insieme fanno 4 + 1 + 2 = 7, che è meno di 8, quindi nessuna scelta può raggiungerlo e la risposta è
false.
Per approfondire
Due valori uguali in posizioni diverse contano come scelte diverse. Quante scelte raggiungono target?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Inizia con
nums[0]. Se lo scegli, gli altri valori devono daretarget-nums[0]. Altrimenti, devono daretarget. È la stessa domanda su un array più corto.Se i valori dalla posizione
iin poi possono dare una sommardipende solo daier, ernon supera maitarget. Quindi ci sono al massimo circa 200 × 10^4 domande diverse, e a ciascuna si può rispondere una sola volta.Usa un booleano per ogni somma da 0 a
target, con inizialmente raggiungibile solo la somma 0. Aggiungi i valori uno alla volta: una sommasdiventa raggiungibile quando lo era giàs-num. Aggiorna le somme dalla più alta alla più bassa, così un valore non viene usato due volte, e leggi la risposta intarget.
Soluzione
Per ogni valore, una scelta può essere sì o no, quindi 200 valori danno 2^200 scelte. Tuttavia, contano solo le somme fino a target ≤ 10^4. Registra quali somme possono essere ottenute finora con i valori: ogni nuovo valore sposta questa registrazione della sua dimensione e la ricerca diventa una tabella di valori booleani n × target.
Prendi o salta ogni valore
Corretto, ma non termina sui test più grandi
Intuizione
canMake(i, remaining) verifica se i valori a partire dalla posizione i possono comporre esattamente remaining. Scegli nums[i] se ci sta, lasciando remaining-nums[i] per il resto; se non funziona, saltalo. Ogni scelta è un percorso, quindi la ricerca trova una scelta ogni volta che ne esiste una.
Quando non ne esiste nessuna, li percorre tutti. Con 200 multipli di 3, ciascuno al massimo pari a 300, e un obiettivo di 9998, nessuna scelta funziona, eppure qualsiasi 33 valori restano sotto l'obiettivo: oltre 10^37 percorsi.
Algoritmo
- Scrivi
canMake(i, remaining). - Un valore di
remainingpari a 0 significa che la scelta è completa: restituisci true. Se non restano valori e c'è ancora qualcosa da ottenere, restituisci false. - Se
nums[i] ≤ remainingecanMake(i+1, remaining-nums[i])è true, restituisci true. - Altrimenti restituisci
canMake(i+1, remaining). - Restituisci
canMake(0, target).
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)Compila una tabella delle somme raggiungibili
Intuizione
La ricorsione dipende solo da una posizione e da una somma rimanente compresa tra 0 e target, e molti percorsi raggiungono la stessa coppia. Invece, riempi una tabella. made[i][s] è true quando una selezione dei primi i valori dà esattamente la somma s; la selezione vuota dà 0. Con num = nums[i-1], la somma s è ottenibile se lo era senza num, made[i-1][s], oppure se num completa s-num, made[i-1][s-num], con s ≥ num.
Nel primo esempio, dopo l’8 le somme ottenibili sono 0 e 8. Il 3 aggiunge 3 e 11, l’11 aggiunge solo 14, il 5 aggiunge 5 e 13, e 8 + 7 raggiunge 15. Ai limiti, la tabella ha 201 × 10001 celle, circa 2 × 10^6 passaggi.
Algoritmo
- Alloca
madecome n+1 righe per target+1 valori booleani, tutti false. Impostamade[0][0]su true per la scelta vuota. - La riga
igestisce il valorenum = nums[i-1], peri= 1 fino a n. - Per ogni somma
sda 0 atarget, impostamade[i][s]amade[i-1][s]. - Se
s ≥ numemade[i-1][s-num]è true, impostamade[i][s]su true. - Restituisci
made[n][target].
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]Una riga di somme, aggiornata dall'alto
Intuizione
Ogni riga legge solo la riga precedente, quindi è sufficiente un array made[s] per contenerla. Sovrascrivilo procedendo verso l’alto e un valore si alimenterà da solo: con nums = [5] e target 10, s = 5 diventa true, poi s = 10 legge quella voce appena aggiornata, usando il 5 due volte.
Procedi invece da target a ritroso fino a num. La lettura in s-num raggiunge una cella più in basso che il percorso non ha ancora riscritto, quindi vede la riga precedente a num. Una somma già ottenibile resta tale, quindi puoi fermarti non appena made[target] è true. La memoria si riduce a target + 1 valori booleani.
Algoritmo
- Inizia con un singolo array di
target + 1valori booleani, in cui solomade[0]è true. - Prendi i valori in ordine. Per ogni
num, fai scenderesdatargetanum. - Ogni volta che
made[s-num]è true, contrassegnamade[s]. - Fermati restituendo
truenon appenamade[target]viene contrassegnato. - Se prima vengono usati tutti i valori, la risposta è
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
Trappole e casi limite
- Un ciclo crescente sulle somme usa un valore due volte:
[3]con obiettivo 9 restituisce vero. - Dimenticare
made[0] = true. Ogni somma si basa sulla scelta vuota, quindi ogni risposta risulta falsa. - Scegliere prima i valori più grandi. Con
[6, 5, 5]e obiettivo 10, prendere 6 lascia 4, che non si può ottenere, mentre 5 + 5 = 10. - Un valore maggiore di
target, come in[10000]con obiettivo 1, non deve cambiare nulla. Swift'snum...targetarresta il programma e R's(num+1):(target+1)conta all'indietro, quindi controlla primanum ≤ target. - In Lua e R la voce per la somma
ssi trova all'indices + 1.
Domande frequenti4
Qual è la complessità temporale del problema della somma di un sottoinsieme?
La tabella richiede un tempo O(n × target), circa 2 × 10^6 passaggi per 200 valori e un target di 10^4, e una sola riga riduce la memoria a O(target). Il costo dipende dalla dimensione numerica del target, quindi il metodo è pseudopolinomiale e inutile per un target come 10^18. In generale, la somma di sottoinsiemi è NP-completa.
In che modo Subset Sum è correlato a Partition Equal Subset Sum e allo zaino 0/1?
Partition Equal Subset Sum è Subset Sum con target = total / 2, dopo aver verificato che il totale sia pari. Subset Sum è uno zaino 0/1 in cui ogni valore è il proprio peso e lo zaino deve essere riempito esattamente, quindi la tabella contiene valori booleani invece dei valori migliori.
Il problema della somma di un sottoinsieme funziona con numeri negativi?
L’idea funziona, il codice qui sopra no. Con i numeri negativi, le somme raggiungibili vanno dalla somma di tutti i negativi alla somma di tutti i positivi, quindi sposta ogni indice aggiungendo la somma più bassa e riempi la riga nello stesso modo. Un valore maggiore della somma rimanente non può più essere saltato.
Come trovi i valori che raggiungono il bersaglio?
Mantieni l’intera tabella e inizia da made[n][target]. Sali di una riga alla volta: se made[i-1][s] è true, nums[i-1] non era necessario; altrimenti, annotalo e sottrailo da s. Ti fermi alla somma 0 con una scelta valida.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isSubsetSum(nums, target):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
nums = [8, 3, 11, 5, 7] target = 15
Output atteso
true