Somma obiettivo con segni positivi e negativi

Dato un array di interi nums e un intero target, assegni un segno + o - a ogni numero in modo che l'espressione risultante abbia valore target. Restituisca il numero di modi distinti per farlo. Per esempio, con nums=[1,1,1,1,1] e target=3, esistono 5 modi: si scelgono 4 elementi a cui assegnare il segno positivo e 1 a cui assegnare il segno negativo, in posizioni diverse.

Un approccio DFS assegna a ogni numero il segno + oppure - e ricorre, restituendo il conteggio dei nodi foglia che raggiungono target. È corretto, ma ha una complessità temporale O(2^n), quindi esponenziale. Per n=20 si superano già le un milione di chiamate ricorsive. In un colloquio conviene menzionare prima l'approccio DFS, per poi passare rapidamente all'ottimizzazione con la DP.

Aggiunga la memoizzazione alla DFS: lo stato è (index, current_sum). Poiché current_sum può variare da -total a +total, esistono O(n × total) stati distinti. Con la memoizzazione, la DFS viene eseguita in O(n × total) tempo e spazio. È una soluzione corretta e valida nei colloqui, ma la DP basata sulla trasformazione è più elegante e più efficiente in termini di spazio.

Sia P l'insieme dei numeri a cui è assegnato il segno + e N l'insieme di quelli a cui è assegnato il segno -. Allora: sum(P) - sum(N) = target e sum(P) + sum(N) = total. Sommando le due uguaglianze: 2 × sum(P) = target + total, quindi sum(P) = (target + total) / 2. Il problema si riduce a: contare i sottoinsiemi di nums con somma pari a (target + total) / 2. Si tratta esattamente della variante «contare i sottoinsiemi» dello zaino 0/1.

Prima di eseguire la DP, verifichi che: (1) target + total sia pari, altrimenti sum(P) non è un intero e il problema è impossibile; (2) abs(target) > total significa che il target non è raggiungibile, nemmeno assegnando lo stesso segno a tutti gli elementi. Se uno dei due controlli fallisce, restituisca immediatamente 0. Questi controlli gestiscono in modo chiaro i casi limite senza introdurre condizioni speciali all'interno del ciclo della DP.

Per nums=[1,1,1,1,1] e target=3: total=5, new_target=(3+5)//2=4. Contiamo i sottoinsiemi con somma pari a 4 tra [1,1,1,1,1]. Si tratta di C(5,4)=5: scegliamo 4 uni a cui assegnare il segno positivo e assegniamo il segno negativo al quinto, ottenendo 1+1+1+1-1=3. La DP restituisce correttamente 5. La trasformazione riconduce in modo elegante il problema dell'assegnazione dei segni a un problema standard di conteggio dei sottoinsiemi.

Se nums contiene degli zeri, assegnare il segno + o - a uno zero non modifica la somma. Ogni zero raddoppia il numero di assegnazioni valide. La DP gestisce naturalmente questo caso: quando si elabora num=0, il ciclo interno range(new_target, -1, -1) va da new_target fino a 0 e dp[c] += dp[c - 0] = dp[c] raddoppia tutte le somme raggiungibili. Non è necessaria una gestione speciale se si utilizza range(new_target, num-1, -1), che quando num=0 parte da new_target e arriva fino a 0.

La DFS a forza bruta ha complessità O(2^n). La DFS con memoizzazione ha complessità O(n × total) in termini di tempo e O(n × total) in termini di spazio. La DP 1D basata sulla trasformazione ha complessità O(n × new_target) in termini di tempo e O(new_target) in termini di spazio, dove new_target ≤ total. La DP 1D utilizza molto meno spazio rispetto alla memoizzazione, perché elimina la dimensione dell'indice grazie alla trasformazione.

Target Sum riunisce diversi concetti dello zaino: inizia come un problema di assegnazione, si trasforma in subset sum (come Partition Equal Subset Sum) e utilizza lo stesso modello di iterazione all'indietro dello zaino 0/1, ma con il conteggio (come Coin Change II). Padroneggiare questi collegamenti consente di classificare rapidamente nei colloqui i nuovi problemi in base alla loro somiglianza strutturale con modelli già noti.

Casi importanti: (1) target = total: esiste un solo modo, con tutti i segni positivi; (2) target = -total: esiste un solo modo, con tutti i segni negativi; (3) target = 0 con tutti zeri: la risposta è 2^n; (4) total molto grande ma n piccolo: la dimensione dell'array DP 1D è limitata da total/2. Nei colloqui, esponga a voce il passaggio della trasformazione prima di scrivere il codice: è l'intuizione non immediata che distingue i candidati più preparati.

Senza la trasformazione, definiamo dp[i][s] come il numero di modi di assegnare i segni ai primi i numeri per raggiungere la somma s. La somma può essere negativa, quindi la trasliamo di total: utilizziamo dp[i][s + total]. Questo richiede una tabella 2D di dimensione (n+1) × (2*total+1). Sebbene sia corretto, questo approccio utilizza più spazio ed è più difficile da implementare rapidamente sotto la pressione di un colloquio rispetto allo zaino 1D ottenuto dopo la trasformazione.

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

In questa lezione ha imparato che: Target Sum trasforma l'assegnazione dei segni nel conteggio dei sottoinsiemi con somma pari a (target + total) / 2, l'iterazione all'indietro dello zaino 0/1 1D conta i sottoinsiemi in O(n × new_target) tempo e O(new_target) spazio e i controlli di validità anticipati (somma dispari, |target| > total) evitano di eseguire inutilmente la DP. Nel prossimo argomento entreremo nel territorio dei cammini minimi con l'algoritmo di Dijkstra e una coda con priorità.