Partition Equal Subset Sum
Ti viene fornito un array nums di interi positivi. Decidi se puoi dividere i valori in due gruppi con somme uguali. Ogni valore va in esattamente un gruppo e un gruppo può contenere valori provenienti da qualsiasi posizione. Restituisci true se esiste una divisione di questo tipo e false altrimenti.
Funzione
- numsinteger-array
- i valori positivi da dividere in due gruppi
- Restituisceboolean
- true quando i valori possono formare due gruppi con somme uguali, false altrimenti
Vincoli
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100
Esempi
- Input
- nums = [6, 1, 4, 9, 2]
- Output
- true
- Spiegazione
- Il totale è 22, quindi ogni gruppo deve avere 11. I gruppi 9 + 2 e 6 + 1 + 4 fanno entrambi 11, quindi la risposta è
true.
- Input
- nums = [4, 7, 2, 9, 6]
- Output
- false
- Spiegazione
- Il totale è 28, quindi ogni gruppo deve averne 14. Al gruppo che ne ha 9 ne servono altri 5, e nessuna combinazione di 4, 7, 2 e 6 dà 5, quindi la risposta è
false, anche se il totale è pari.
- Input
- nums = [1, 2, 3, 5]
- Output
- false
- Spiegazione
- Il totale è 11. Due numeri interi uguali danno sempre come somma un numero pari, quindi un totale dispari non può mai essere diviso e la risposta è
false.
Per approfondire
Quando non esiste una suddivisione equa, puoi restituire la differenza più piccola possibile tra le somme dei due gruppi?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Se i due gruppi hanno somme uguali, quanto deve essere ciascuna somma in termini del totale di
nums? E cosa ti dice subito un totale dispari?Devi solo trovare un gruppo la cui somma sia pari alla metà del totale; i valori rimanenti formano l'altro gruppo. Pensa all'insieme delle somme che i primi valori possono raggiungere e a come un altro valore modifica quell'insieme.
Mantieni un array booleano
reach[0..target]con soloreach[0]impostato su true. Per ogni valorenum, percorrisdatargetfino anume contrassegnareach[s]quandoreach[s-num]è contrassegnato. Procedere in ordine decrescente evita che ogni valore venga usato due volte.
Soluzione
Ogni gruppo deve contenere esattamente la metà del totale, quindi la vera domanda è se qualche sottoinsieme di nums ha una somma pari a target = total / 2. Provare tutti i sottoinsiemi richiede 2^n tentativi, un numero ingestibile per 200 valori. Le somme, però, sono piccole: target è al massimo 200 × 100 / 2 = 10^4. Registrare quali somme sono raggiungibili, un valore alla volta, trasforma la ricerca in una tabella dello zaino 0/1 che si completa in O(n × sum) passaggi.
Prova ogni sottoinsieme con la ricorsione
Corretto, ma non termina sui test più grandi
Intuizione
Inizia con il totale. Se è dispari, non esiste alcuna suddivisione, perché due numeri interi uguali sommati danno un numero pari. Altrimenti, ogni gruppo deve raggiungere esattamente target = total / 2. Una volta trovati valori che raggiungono target, i valori che non hai scelto formano da soli l’altra metà. Quindi basta porsi una domanda: esiste un sottoinsieme che raggiunge target?
Esamina i valori in ordine e fai una scelta per ciascuno: inserirlo nel primo gruppo oppure lasciarlo per il secondo. Una funzione ausiliaria reach(i, remaining) indica se i valori a partire dall’indice i possono sommare a remaining. Restituisce true quando remaining raggiunge 0, false quando non ci sono più valori o scende sotto 0; altrimenti prova entrambe le scelte per nums[i].
Ogni sottoinsieme corrisponde a un percorso di scelte, quindi la ricerca non può tralasciare una suddivisione e la risposta è corretta. È lenta perché ci sono 2^n percorsi e, se l’input non ammette suddivisioni, deve provarne quasi tutti. Prendi 199 copie di 100 e un 98: il totale è 19998, il valore target 9999 non viene mai raggiunto e la ricerca prova ogni modo di scegliere al massimo 99 dei valori 100, circa 4 × 10^59 percorsi. Anche 40 valori danno 2^40, circa 10^12 percorsi.
Algoritmo
- Somma
nums. Se il totale è dispari, restituiscifalse. - Imposta
targetalla metà del totale. - Scrivi
reach(i, remaining): restituisci true quandoremainingè 0 e false quandoisupera l’ultimo valore oremainingè minore di 0. - Altrimenti restituisci
reach(i+1, remaining-nums[i])oppurereach(i+1, remaining): prendi il valore oppure lascialo. - Restituisci
reach(0, target).
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
# Can some of the values from index i on add up to exactly remaining?
def reach(i, remaining):
if remaining == 0:
return True
if i == len(nums) or remaining < 0:
return False
# Put nums[i] in the first group, or leave it for the second one
return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)
return reach(0, total // 2)Compila una tabella per valore e somma
Intuizione
La ricorsione pone la stessa domanda più e più volte. reach(i, remaining) dipende solo da due numeri: i da 0 a n e remaining da 0 a target. Questo dà al massimo (n+1) × (target+1) domande diverse, circa 201 × 10001 ≈ 2 × 10^6 ai limiti: abbastanza poche da poter rispondere a ciascuna una sola volta.
Costruisci le risposte in avanti in una tabella. can[i][s] indica se alcuni dei primi i valori sommano s. Senza valori, è possibile solo la somma 0, quindi la riga 0 è falsa tranne per can[0][0]. Il valore num = nums[i-1] offre due modi per raggiungere s: escludere num, quindi i valori precedenti raggiungono già s, oppure includerlo, quindi i valori precedenti raggiungono s-num. Questa è l’intera regola: can[i][s] = can[i-1][s] or can[i-1][s-num], dove la seconda parte conta solo quando s ≥ num. Ogni riga legge solo quella sopra, quindi ogni valore viene usato al massimo una volta.
Con [6, 1, 4, 9, 2] e target 11, le somme raggiungibili aumentano da {0} a {0, 6}, poi {0, 1, 6, 7}, quindi {0, 1, 4, 5, 6, 7, 10, 11}. La somma 11 compare dopo il 4 (6 + 1 + 4), e le righe successive la mantengono. La risposta è can[n][target]. Ogni cella richiede un lavoro costante, quindi tempo e memoria sono entrambi O(n × target).
Algoritmo
- Restituisci
falsese il totale è dispari e impostatargetalla sua metà. - Crea una tabella con n+1 righe e target+1 colonne, tutte false, e imposta
can[0][0]su true. - Per ogni riga
ida 1 a n, prendinum = nums[i-1]. - Per ogni somma
sda 0 atarget, impostacan[i][s]sucan[i-1][s]oppure, quandos ≥ num, sucan[i-1][s-num]. - Restituisci
can[n][target].
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
n = len(nums)
# can[i][s] is True when some of the first i values add up to s
can = [[False] * (target + 1) for _ in range(n + 1)]
can[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 and reach s - num with the values before it
can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
return can[n][target]Una riga di somme, riempita dall'alto verso il basso
Intuizione
Ogni riga della tabella legge solo la riga che la precede, quindi basta una sola riga se la aggiorni sul posto: reach[s] indica se alcuni dei valori considerati finora danno come somma s. Il rischio sta nell’ordine degli aggiornamenti. Se scorri s verso l’alto, reach[s-num] potrebbe essere già stato attivato dallo stesso num. Con [3, 9] e target 6, il 3 segna reach[3], poi lo legge per segnare reach[6], come se avessi due 3, e rispondi vero per una divisione che non esiste.
Scorri s verso il basso, da target a num. Così s-num è un indice più piccolo che questo valore non ha ancora toccato, quindi reach[s-num] contiene ancora la risposta di prima che arrivasse num. È esattamente can[i-1][s-num] della tabella, e la singola riga svolge il lavoro dell’intera tabella.
Puoi anche fermarti non appena reach[target] diventa vero, perché i valori successivi aggiungono solo somme raggiungibili, senza mai rimuoverne. Nel caso peggiore servono comunque O(n × target) passaggi, circa 2 × 10^6, e la memoria si riduce a target + 1 valori booleani.
Algoritmo
- Restituisci
falsese il totale è dispari e impostatargetalla sua metà. - Crea
reachcontarget + 1elementi, tutti false trannereach[0]. - Per ogni valore
num, percorrisdatargetfino anume impostareach[s]su true quandoreach[s-num]è true. - Dopo ogni valore, restituisci
truesereach[target]è true. - Se il ciclo termina, restituisci
reach[target], che è false.
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
# reach[s] is True when some of the values seen so far add up to s
reach = [False] * (target + 1)
reach[0] = True
for num in nums:
# Walk the sums downward so num is used at most once
for s in range(target, num - 1, -1):
if reach[s - num]:
reach[s] = True
if reach[target]:
return True
return reach[target]
Trappole e casi limite
Le risposte errate qui derivano dall’affidarsi a una strategia greedy, dal saltare il controllo della disparità e dal riutilizzare un valore nella tabella a una riga.
- Scorrere le somme verso l’alto nella versione a una riga usa un valore più di una volta. Con
[3, 9]l’obiettivo è 6, il 3 segna prima la somma 3 e poi la somma 6, e la risposta è true. - Saltare il controllo della disparità: per
[1, 2]il totale 3 viene arrotondato per difetto a un obiettivo di 1, il valore 1 lo raggiunge e la risposta è true per una divisione che non può esistere. - Riempire in modo greedy, per esempio ordinando e aggiungendo sempre al gruppo più leggero, non funziona con
[3, 3, 2, 2, 2]: si finisce con 7 contro 5, mentre 3 + 3 = 2 + 2 + 2. - Un valore maggiore dell’obiettivo, come in
[2, 2, 2, 10]. Un ciclo decrescente datargetanumviene quindi eseguito zero volte, il che è corretto, ma un intervallo come(num+1):(target+1)in R procede all’indietro e compromette la tabella. Salta questi valori. - Un totale pari non è sufficiente:
[4, 7, 2, 9, 6]dà come somma 28 e non ha comunque una divisione. - In Lua e R gli array iniziano da 1, quindi la voce per la somma
ssi trova all’indices + 1.
Domande frequenti3
Perché Partition Equal Subset Sum è un problema di zaino 0/1?
Hai uno zaino di capacità target = total / 2 e devi riempirlo esattamente, usando ogni valore al massimo una volta. Prendere o lasciare un valore è la scelta 0/1 e la dimensione di un valore coincide con il valore stesso. La tabella dello zaino delle somme raggiungibili risolve il problema in tempo O(n × target).
Qual è la complessità temporale del problema della partizione in sottoinsiemi di somma uguale?
L’approccio con tabella richiede un tempo O(n × target), dove target è la metà del totale, e una memoria O(target) con una sola riga. Con 200 valori al massimo pari a 100, sono circa 2 × 10^6 passaggi. Il limite cresce con la dimensione dei valori, non solo con il loro numero, perciò si parla di pseudopolinomiale: con valori vicini a 10^9, nessuna tabella potrebbe starci, e il problema generale è NP-completo.
Perché il ciclo interno va dal valore obiettivo fino al valore?
Scorrere verso il basso significa che reach[s-num] viene letto prima che questo valore possa modificarlo, quindi descrive ancora i valori precedenti a num. Scorrere verso l’alto permetterebbe a una somma costruita con num di essere estesa di nuovo usando num, contando così lo stesso valore più volte. Il ciclo verso l’alto è quello giusto per copie illimitate, come in Coin Change, ma qui è quello sbagliato.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def canPartition(nums):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
nums = [6, 1, 4, 9, 2]
Output atteso
true