Somma di sottoinsiemi con partizione equa

Dato un array non vuoto di interi positivi nums, stabilisca se è possibile suddividerlo in due sottoinsiemi con somma uguale. Ad esempio, [1, 5, 11, 5] può essere suddiviso in [1, 5, 5] e [11], entrambi con somma pari a 11. Se la somma totale è dispari, la risposta è immediatamente False. Altrimenti, è necessario trovare un sottoinsieme la cui somma sia total_sum // 2: un classico problema di subset sum.

La riduzione chiave: se la somma totale S è pari e un sottoinsieme ha somma S//2, anche gli elementi rimanenti hanno automaticamente somma S//2. Quindi Partition Equal Subset Sum si riduce alla domanda: esiste un sottoinsieme di nums la cui somma è S//2? Questo è il classico problema NP-completo Subset Sum, che risolviamo con la programmazione dinamica dello zaino 0/1 in tempo O(n × S).

Definisca un array booleano dp[c], dove dp[c] = True significa che esiste un sottoinsieme con somma esattamente pari a c. Inizializzi dp[0] = True (il sottoinsieme vuoto ha somma 0) e tutti gli altri valori a False. Per ogni numero num, iteri sulla capacità da target fino a num (iterazione all'indietro dello zaino 0/1) e imposti dp[c] = dp[c] or dp[c - num].

Per [1, 5, 11, 5], total=22 e target=11. Inizialmente dp[0]=True. Dopo num=1: dp[1]=True. Dopo num=5: dp[5]=True, dp[6]=True. Dopo num=11: dp[11]=True (usando solo 11). Abbiamo già trovato dp[11]=True, ma continuiamo a elaborare tutti i numeri. Risposta finale: dp[11]=True, quindi la partizione è possibile.

Possiamo aggiungere un'uscita anticipata: se dp[target] diventa True in un qualsiasi momento, restituiamo immediatamente True. Questo può velocizzare notevolmente i casi migliori. Inoltre, se un singolo elemento è uguale a target, possiamo restituire subito True. Se un singolo elemento supera target, non può appartenere ad alcun sottoinsieme con somma pari a target, ma dobbiamo comunque verificare gli elementi rimanenti.

Un'alternativa consiste nel mantenere un set delle somme raggiungibili. Si parte da {0}. Per ogni numero, lo si aggiunge a ogni somma presente nel set corrente: reachable = reachable | {s + num for s in reachable}. Filtri il risultato per conservare solo le somme che non superano target. Alla fine, verifichi se target appartiene al set. Questo approccio è intuitivo, ma può richiedere più memoria e risultare più lento nella pratica.

L'approccio DP viene eseguito in O(n × S) tempo, dove S = sum(nums), e utilizza O(S) spazio per l'array booleano. Per i vincoli di LeetCode (n ≤ 200, somma ≤ 20.000), si tratta al massimo di 4.000.000 di operazioni: è molto veloce. L'approccio con il set ha la stessa complessità asintotica, ma può essere più lento nella pratica a causa del costo di costruzione dei set.

Un problema correlato consiste nel contare il numero di sottoinsiemi con somma pari a un target. Si trasformi la DP da booleana a intera: dp[c] = number of ways to reach sum c. Utilizzi l'addizione al posto dell'OR: dp[c] += dp[c - num]. Inizializzi dp[0] = 1. L'iterazione all'indietro rimane invariata. Questa generalizzazione mostra come il modello dello zaino possa adattarsi a domande diverse sui sottoinsiemi.

Si aspetti domande di approfondimento: (1) Cosa fare se occorre restituire la partizione effettiva? — è necessaria una DP 2D per la ricostruzione. (2) Cosa fare se gli elementi possono essere negativi? — si sposti il target oppure si utilizzi un dizionario invece di un array. (3) Qual è la complessità temporale? — O(n × somma). (4) È possibile migliorare la soluzione se molti numeri sono uguali? — sì, si utilizzi il conteggio delle frequenze per ridurre il numero di iterazioni esterne. Menzioni sempre questi compromessi in modo proattivo.

Partition Equal Subset Sum è un'applicazione diretta dello zaino 0/1: gli elementi sono i numeri, i pesi sono uguali ai valori e la capacità dello zaino è uguale al target. Verifichiamo se il valore massimo è uguale al target (un problema di fattibilità), non quale sia il valore massimo. L'iterazione all'indietro è la stessa; cambia solo l'operazione, da max a or booleano. Riconoscere questo collegamento durante un colloquio dimostra una solida capacità di individuare i modelli ricorrenti.

Gestisca i seguenti casi limite: (1) array di lunghezza 1: un singolo elemento non può essere diviso in due parti, quindi il risultato è sempre False; (2) tutti gli elementi identici e in quantità pari: la soluzione può esistere oppure no, a seconda dei singoli valori; (3) somme molto grandi: verifichi i vincoli prima di allocare l'array DP; (4) elementi più grandi del target: possono essere ignorati, perché non possono mai far parte di un sottoinsieme con somma pari al target. Il controllo sull'elemento massimo come uscita anticipata gestisce il caso (4) in modo efficiente.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

In questa lezione ha imparato che: Partition Equal Subset Sum si riduce a subset sum con target = total//2, la DP 1D booleana dp[c] utilizza l'iterazione all'indietro, identica a quella dello zaino 0/1 e l'approccio si generalizza al conteggio dei sottoinsiemi sostituendo l'OR booleano con l'addizione tra interi. Nel prossimo argomento affronteremo Target Sum, trasformando l'assegnazione dei segni in un problema di zaino sulla differenza tra le somme dei sottoinsiemi.