Target Sum

Q: In che modo Target Sum è correlato al problema della somma dei sottoinsiemi?

I numeri con il segno più devono avere una somma pari a (S + target) / 2 , quindi la risposta è il numero di sottoinsiemi di nums con quella somma. Qualsiasi programmazione dinamica per contare le somme dei sottoinsiemi risolve il problema una volta aggiunti due controlli: il valore deve essere un numero intero e |target| non deve superare S .

MedioProgrammazione dinamica Backtracking

+10

Ricevi un array nums di interi non negativi e un intero target. Metti un segno più o meno davanti a ogni numero, mantieni il loro ordine e valuta l'espressione. Restituisci quanti modi di scegliere i segni rendono l'espressione uguale a target. Ognuna delle 2^n scelte conta separatamente, quindi +0 e -0 sono due scelte diverse.

Funzione

findTargetSumWays(nums: integer-array, target: integer) → integer

numsinteger-array: i numeri, ognuno dei quali ha un segno
targetinteger: il valore a cui l’espressione deve essere uguale
Restituisceinteger: il numero di opzioni di segno la cui espressione è uguale al valore target

Vincoli

1 ≤ nums.length ≤ 20
0 ≤ nums[i] ≤ 1000
La somma di nums è al massimo 1000.
-1000 ≤ target ≤ 1000
La risposta è al massimo 2²⁰, ben al di sotto del limite di un intero con segno a 32 bit.

Esempi

Input: nums = [2, 1, 1]target = 2
Output: 2
Spiegazione: +2 +1 -1 e +2 -1 +1 sono entrambi uguali a 2. Con un meno sul 2, il massimo che puoi ottenere è -2 + 1 + 1 = 0, quindi nessun’altra scelta funziona.

Input: nums = [0, 4, 4]target = 0
Output: 4
Spiegazione: I due 4 devono avere segni opposti, +4 -4 oppure -4 +4, e in entrambi i casi lo 0 può avere segno qualsiasi. Questo dà 2 × 2 = 4 possibilità.

Per approfondire

Riesci a gestire fino a 40 numeri con valori fino a 10^9, quando nessun array indicizzato per somma entra in memoria?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni numero ha due segni, quindi ci sono 2^n espressioni. Contare in base alla posizione e al totale parziale unisce i prefissi di segni che raggiungono lo stesso totale. Ancora meglio, i numeri con il segno più formano un sottoinsieme con una somma fissa, quindi il problema diventa contare i sottoinsiemi con una determinata somma, in O(n × S) tempo, dove S è la somma di nums.

Prova entrambi i segni per ogni numero

Corretto, ma non termina sui test più grandi

Intuizione

Esamina i numeri da sinistra a destra tenendo un totale progressivo e, per ciascuno, crea due diramazioni: aggiungerlo oppure sottrarlo. Quando ogni numero ha un segno, conta 1 se il totale è uguale a target. Ogni scelta del segno corrisponde a un unico percorso, quindi la somma dei conteggi dà la risposta.

Questo significa un nodo foglia per ogni scelta: 2^20 ≈ 10^6 nodi foglia per 20 numeri, e ogni numero in più raddoppia il lavoro.

Algoritmo

Scrivi count(i, total), il numero di modi per assegnare un segno a nums[i..] quando i numeri prima di i hanno già somma total.
Se i == n, restituisci 1 quando total == target, altrimenti 0.
Altrimenti restituisci count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
La risposta è count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)

    def count(i, total):
        # Ways to sign nums[i:] so that the whole expression ends at target
        if i == n:
            return 1 if total == target else 0
        return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])

    return count(0, 0)

Memorizza la posizione e il totale parziale

Intuizione

count(i, total) dipende solo da i e total, non dai segni che hanno prodotto il totale. Con nums = [1, 1, 1, 1], i prefissi +1 -1 e -1 +1 raggiungono entrambi il totale 0 alla posizione 2, quindi la ricerca da quel punto è la stessa. Memorizza ogni risultato la prima volta e riutilizzalo.

Il totale corrente resta tra -S e S, quindi traslalo di S per usarlo come indice: memo[i][total + S]. Ci sono al massimo n × (2S+1) stati, circa 4 × 10^4 per 20 numeri la cui somma è 1000, ciascuno con un lavoro costante.

Algoritmo

Calcola S = sum(nums) e crea una tabella n × (2S+1) di valori memo inizializzata con -1.
In count(i, total), restituisci il caso base quando i == n, come prima.
Se memo[i][total + S] è -1, impostalo a count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
Restituisci il valore memorizzato e chiama count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)
    whole = sum(nums)
    # memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
    memo = [[-1] * (2 * whole + 1) for _ in range(n)]

    def count(i, total):
        if i == n:
            return 1 if total == target else 0
        if memo[i][total + whole] == -1:
            memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
        return memo[i][total + whole]

    return count(0, 0)

Conta i sottoinsiemi la cui somma è (S + target) / 2

Intuizione

Sia P la somma dei numeri con segno più e N quella dei restanti. Allora P - N = target e P + N = S, quindi 2P = S + target. Una scelta dei segni funziona esattamente quando il suo gruppo con il segno più ha somma pari a (S + target) / 2, e ciascuno di questi sottoinsiemi corrisponde a una scelta dei segni.

ways[s] conta i sottoinsiemi dei numeri considerati finora la cui somma è s, partendo da ways[0] = 1. Per ogni numero x, un sottoinsieme che raggiunge s o non include x oppure lo aggiunge a un sottoinsieme che raggiunge s - x. Procedi dal valore s più grande verso il più piccolo, così ways[s - x] conserva ancora il valore che aveva prima di x e nessun numero viene usato due volte. Uno 0 aggiunge ogni voce a sé stessa, raddoppiando tutti i conteggi: i due segni di uno zero. Si tratta di n × goal addizioni, al massimo 2 × 10^4.

Algoritmo

Calcola S = sum(nums). Se |target| > S o S + target è dispari, restituisci 0.
Imposta goal = (S + target) / 2, crea ways con goal + 1 zeri e imposta ways[0] = 1.
Per ogni x in nums, per s da goal fino a x in ordine decrescente, aggiungi ways[s - x] a ways[s].
Restituisci ways[goal].

def findTargetSumWays(nums, target):
    whole = sum(nums)
    # plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
    if abs(target) > whole or (whole + target) % 2 == 1:
        return 0
    goal = (whole + target) // 2
    # ways[s]: how many subsets of the values seen so far add up to s
    ways = [0] * (goal + 1)
    ways[0] = 1
    for x in nums:
        # From the top down, so each value is used at most once
        for s in range(goal, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[goal]

Trappole e casi limite

Saltare il controllo della parità. Per [6, 3] e target 4, (9 + 4) / 2 viene arrotondato per difetto a 6 e il sottoinsieme {6} dà 1 invece di 0.
Saltare il controllo dell’intervallo. Per [1, 2, 3] e target -10, (6 - 10) / 2 = -2, una dimensione negativa dell’array.
Riempire ways dal basso verso l’alto. In questo modo un numero viene aggiunto a un sottoinsieme che lo usa già: [1, 3] con target 2 restituisce 2 invece di 1.
Considerare uno zero come una sola scelta. [0, 0, 0, 1, 0, 0] con target -1 ha 32 risposte, una per ogni schema di segni dei cinque zeri.
Usare un totale progressivo negativo come indice per una tabella di memoizzazione. Sposta ogni totale di S oppure usa una mappa hash.

Domande frequenti3

In che modo Target Sum è correlato al problema della somma dei sottoinsiemi?

I numeri con il segno più devono avere una somma pari a (S + target) / 2, quindi la risposta è il numero di sottoinsiemi di nums con quella somma. Qualsiasi programmazione dinamica per contare le somme dei sottoinsiemi risolve il problema una volta aggiunti due controlli: il valore deve essere un numero intero e |target| non deve superare S.

Qual è la complessità temporale di Target Sum?

La programmazione dinamica per il conteggio dei sottoinsiemi ha una complessità temporale di O(n × S) e usa O(S) memoria, dove S è la somma di nums. La ricorsione con memoizzazione ha la stessa complessità temporale, ma usa una tabella n × (2S+1). Provare ogni segno ha una complessità di O(2^n).

È possibile risolvere Target Sum con una mappa hash dei totali parziali?

Sì. Associa a ogni somma parziale raggiungibile il numero di prefissi di segni che la raggiungono, iniziando con {0: 1}, e costruisci la mappa successiva a partire da total + x e total - x per ogni numero. La risposta è il conteggio in corrispondenza di target. È la ricorsione con memoizzazione eseguita in avanti, con la stessa complessità temporale O(n × S).

def findTargetSumWays(nums, target):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

nums = [2, 1, 1]
target = 2

Output atteso

Target Sum

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova entrambi i segni per ogni numero

Memorizza la posizione e il totale parziale

Conta i sottoinsiemi la cui somma è (S + target) / 2

Trappole e casi limite

Domande frequenti3

Problemi simili