Combination Sum

Q: Perché in Combination Sum ricorri con i e non con i + 1?

La ricorsione con i permette che il valore successivo sia di nuovo lo stesso candidato, ed è così che un valore viene usato più di una volta. La ricorsione con i + 1 lo supera, trasformando il problema nella variante in cui ogni candidato viene usato al massimo una volta. L’altra metà della regola è altrettanto importante: non tornare mai a un indice precedente a i mantiene ogni combinazione in ordine crescente ed evita i duplicati.

MedioBacktracking

+10

Hai un elenco candidates di diversi interi positivi e un intero positivo target. Trova tutte le combinazioni di candidati i cui valori sommano esattamente a target, dove ogni candidato può essere usato tutte le volte che vuoi. Due combinazioni sono uguali quando contengono gli stessi valori lo stesso numero di volte, quindi [2, 3, 3] e [3, 2, 3] contano come una sola.

Restituisci ogni combinazione con i valori in ordine crescente e le combinazioni in ordine lessicografico: confronta due combinazioni valore per valore da sinistra, e quella con il valore più piccolo alla prima differenza viene prima.

Funzione

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: i diversi valori che puoi usare, in qualsiasi ordine e tutte le volte che vuoi
targetinteger: il totale di ogni combinazione deve arrivare esattamente
Restituisceinteger-2d-array: ogni combinazione la cui somma è uguale al valore obiettivo, in ordine crescente e ordinate lessicograficamente

Vincoli

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Tutti i valori in candidates sono diversi, in nessun ordine particolare.
Almeno una combinazione raggiunge target, e al massimo 150 lo fanno.

Esempi

Input: candidates = [6, 2, 3]target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Spiegazione: Quattro 2 fanno 8, così come 2 + 3 + 3 e 2 + 6. Tutte e tre le combinazioni iniziano con 2, quindi è il secondo valore a stabilire l’ordine: 2, poi 3, poi 6. Senza un 2 hai solo 3 e 6, e ogni combinazione di questi è un multiplo di 3, cosa che 8 non è.

Input: candidates = [5, 3, 4]target = 11
Output: [[3, 3, 5], [3, 4, 4]]
Spiegazione: 3 + 3 + 5 e 3 + 4 + 4 fanno entrambi 11. Corrispondono al primo valore e, al secondo, il 3 è minore del 4, quindi [3, 3, 5] viene prima. Nessuna combinazione di soli 4 e 5 dà 11.

Input: candidates = [4, 9]target = 9
Output: [[9]]
Spiegazione: 9 da solo è una combinazione. I 4 danno solo 4, 8 e 12 passando per 9, e 4 + 9 è già 13, quindi [9] è l’unica risposta.

+12 test nascosti all’invio

Per approfondire

Ora ogni candidato può essere usato al massimo una volta e candidates può contenere valori ripetuti. Come modifichi la ricerca affinché nessuna combinazione compaia due volte?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni risposta è un multinsieme di candidati, e la trappola consiste nel costruire più di una volta lo stesso multinsieme: scegliere 2, poi 3, poi 3 e scegliere 3, poi 2, poi 3 portano alla stessa combinazione. L’idea che risolve il problema è costruire ogni combinazione in ordine crescente, così da avere esattamente un solo modo per costruirla, e ordinare i candidati in modo che un ramo si interrompa non appena il valore successivo è maggiore di ciò che resta. Lo stesso percorso crescente fornisce le combinazioni in ordine lessicografico, senza bisogno di un ordinamento finale.

Prova ogni conteggio di ogni candidato

Corretto, ma non termina sui test più grandi

Intuizione

Una combinazione è descritta completamente dal numero di copie di ciascun candidato che utilizza. Per [6, 2, 3] e target 8, la risposta [2, 3, 3] è composta da un 2, due 3 e nessun 6. Un modo per trovare ogni risposta è quindi provare ogni possibile quantità per ciascun candidato e mantenere le scelte la cui somma è esattamente target. Un candidato c può essere usato al massimo target / c volte, quindi la sua quantità va da 0 a quel limite.

Immagina un albero decisionale con un livello per ogni candidato, dopo averli ordinati. Al livello i decidi quante copie del valore in posizione i prendere, e ogni foglia in fondo rappresenta una scelta completa di quantità. Ogni multinsieme ha esattamente un elenco di quantità, quindi nessuna combinazione viene trovata due volte. Provare prima la quantità maggiore dà anche l’ordine richiesto: quando due risposte differiscono per la prima volta nella quantità di un certo valore, quella con più copie conserva quel valore piccolo, mentre l’altra ha già un valore più grande, quindi viene prima.

Il problema è la dimensione dell’albero. Il numero di foglie è il prodotto di target / c + 1 per tutti i candidati: per [2, 3, 6] ordinato e target 8, sono 5 × 3 × 2 = 30 foglie per 3 risposte. Ogni candidato maggiore di target / 2 raddoppia il numero di foglie, anche se può essere usato al massimo una volta, quindi 40 candidati di questo tipo da soli significano 2^40, circa 10^12, foglie. I test grandi sono costruiti in questo modo e questo approccio non riesce a completarli.

Algoritmo

Ordina i candidati e crea un array di conteggi, uno per ogni valore.
Scrivi choose(i, total), che fissa il conteggio del valore all'indice i.
Per k da target / nums[i] fino a 0, imposta il conteggio a k e chiama choose(i + 1, total + k × nums[i]).
Quando ogni valore ha un conteggio, conserva la combinazione se total è uguale a target, scrivendo ogni valore tante volte quanto indicato dal suo conteggio.
Chiama choose(0, 0). Le combinazioni conservate sono già in ordine lessicografico.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Ripercorri a ritroso in ordine crescente e pota

Intuizione

Costruisci ogni combinazione un valore alla volta, proprio come la scriveresti: in ordine crescente. L’indice iniziale impone quest’ordine. Dopo aver inserito nums[i], il valore successivo può essere di nuovo nums[i], perché un candidato può ripetersi, oppure qualsiasi valore successivo, ma mai uno precedente. Perciò la chiamata che ha inserito l’indice i esegue il ciclo solo da i in poi. Ogni combinazione ha esattamente un ordine crescente, quindi ha un solo percorso nell’albero e non viene mai costruito un duplicato come [3, 2, 3].

Ecco l’intero albero per [2, 3, 6] ordinato e target 8. La radice ha 8 rimanente e prova 2, 3 e 6. Sotto 2 rimangono 6. Sotto 2, 2 rimangono 4, e 2, 2, 2 lascia 2, che un altro 2 trasforma nella risposta [2, 2, 2, 2]; 2, 2, 3 lascia 1 e non porta a una soluzione. Sotto 2, 3 rimangono 3 e puoi provare solo 3 e 6; il 3 dà [2, 3, 3]. Sotto 2, 6 non rimane nulla: [2, 6]. Sotto 3 puoi provare solo 3 e 6, e 3, 3 lascia 2, che non completa la combinazione. Sotto 6 rimangono 2 e puoi provare solo 6. In tutto sono dodici chiamate, contro le 30 foglie del primo approccio.

L’ordinamento trasforma un vicolo cieco in un’interruzione anticipata. Quando nums[i] è maggiore di quanto rimane, anche tutti i valori successivi sono maggiori, quindi esci dal ciclo con break invece di provare il resto. Nell’albero qui sopra, il nodo 2, 2, 3 con 1 rimanente considera 3, vede che non ci sta e non considera mai 6. La ricerca visita solo i prefissi la cui somma è ancora al massimo target, ed è per questo che i test più grandi che mettono in difficoltà il primo approccio richiedono qui solo qualche migliaio di chiamate.

L’ordine dei risultati deriva dalla stessa visita. A ogni livello il ciclo prova prima i valori più piccoli, e ogni combinazione viene scritta in ordine crescente. Due risposte differiscono per la prima volta al livello in cui i loro percorsi si separano, e il percorso con il valore più piccolo in quel punto viene esplorato per primo, quindi le risposte arrivano in ordine lessicografico. Una combinazione non può mai essere il prefisso di un’altra, perché i valori sono positivi ed entrambe raggiungono lo stesso totale.

Algoritmo

Ordina i candidati in ordine crescente.
Scrivi backtrack(start, remaining) che condivida una lista path. Se remaining è 0, salva una copia di path.
Altrimenti, esegui un ciclo con i da start fino alla fine. Se nums[i] > remaining, interrompi: tutti i valori successivi sono maggiori.
Aggiungi nums[i], chiama backtrack(i, remaining-nums[i]) con i, non i + 1, così il valore può ripetersi, poi rimuovilo.
Chiama backtrack(0, target) e restituisci le combinazioni salvate, già in ordine lessicografico.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Trappole e casi limite

La maggior parte delle risposte sbagliate dipende dall’ordine della ricerca, non dai calcoli.

Scorrere ogni candidato a ogni livello, invece di partire dall’indice corrente, crea [2, 3, 3], [3, 2, 3] e [3, 3, 2] come tre risposte. Ordinare ogni risposta e rimuovere i duplicati in seguito dà la lista corretta, ma richiede un lavoro esponenzialmente maggiore.
Ricorrere con i + 1 invece che con i fa sì che ogni valore possa comparire una sola volta, quindi [2, 2, 2, 2] non viene trovato.
Salvare path invece di una copia: ogni risposta salvata diventa la stessa lista, che il backtracking ha svuotato alla fine.
Usare break su candidati che non hai ordinato. Con [6, 2, 3] e 2 rimanenti, il ciclo si ferma a 6 e non prova mai il 2.
Restituire le combinazioni nell’ordine suggerito dall’input non ordinato. La lista prevista è in ordine lessicografico, che la ricerca ordinata produce senza un ordinamento aggiuntivo.
In Lua e R, gli array iniziano da 1, quindi la prima chiamata parte dall’indice 1 e il ciclo arriva fino alla lunghezza dell’array.

Domande frequenti4

Qual è la complessità temporale di Combination Sum?

La ricerca con backtracking è esponenziale. Con n candidati, un obiettivo t e il candidato più piccolo m, una combinazione contiene al massimo t/m valori e ogni passaggio ha al massimo n possibilità, il che limita il lavoro a O(n^(t/m)). Il pruning sui candidati ordinati mantiene il numero effettivo di chiamate molto al di sotto di questo limite, perché la ricerca visita solo prefissi la cui somma è ancora al massimo t. Lo spazio aggiuntivo è O(t/m) per il percorso corrente e lo stack delle chiamate, oltre all'output.

Perché in Combination Sum ricorri con i e non con i + 1?

La ricorsione con i permette che il valore successivo sia di nuovo lo stesso candidato, ed è così che un valore viene usato più di una volta. La ricorsione con i + 1 lo supera, trasformando il problema nella variante in cui ogni candidato viene usato al massimo una volta. L’altra metà della regola è altrettanto importante: non tornare mai a un indice precedente a i mantiene ogni combinazione in ordine crescente ed evita i duplicati.

Come si evitano le combinazioni duplicate senza un insieme?

Genera ogni combinazione in un ordine fisso, crescente. L’indice di partenza lo impone: dopo aver inserito nums[i], la ricerca considera solo nums[i] e i valori successivi. Ogni combinazione ha quindi esattamente un percorso nell’albero di ricerca, perciò viene generata una sola volta e non è necessario usare un insieme né deduplicare alla fine.

È possibile risolvere Combination Sum con la programmazione dinamica?

Sì. Per ogni totale da 0 al target, conserva l’elenco delle combinazioni che lo raggiungono e aggiungi un candidato alla volta, così che i valori di ogni elenco restino in ordine crescente: è la stessa idea del conteggio dei modi per ottenere il resto. Non esplora mai due volte un vicolo cieco, ma memorizza ogni combinazione parziale per ogni totale, il che richiede molta più memoria rispetto al backtracking, e potrebbe essere necessario ordinare l’elenco finale. Poiché l’output stesso può avere dimensioni esponenziali, il backtracking è la risposta più comune.

Python

def combinationSum(candidates, target):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

candidates = [6, 2, 3]
target = 8

Atteso

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]