Combination Sum

Q: 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 con al massimo n scelte ciascuno: O(n^(t/m)) . Lo spazio aggiuntivo è O(t/m) per il percorso e lo stack delle chiamate, oltre all'output.

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

Ricorrere con i permette al valore successivo di essere di nuovo lo stesso candidato, ed è così che un valore viene usato più di una volta. Ricorrere con i + 1 lo supera, quindi ogni candidato può essere usato al massimo una volta.

Q: Si può risolvere Combination Sum con la programmazione dinamica?

Sì. Per ogni totale da 0 a target , conserva le combinazioni che lo raggiungono, aggiungendo un candidato alla volta, così ogni lista rimane in ordine crescente. Non esplora mai due volte un vicolo cieco, ma memorizza ogni combinazione parziale per ogni totale, il che richiede molta più memoria. Poiché l’output stesso può essere esponenziale, il backtracking è la soluzione abituale.

MedioBacktracking

+10

Ti viene fornito un elenco candidates di diversi interi positivi e un intero positivo target. Trova tutte le combinazioni di candidati la cui somma è esattamente target, utilizzando ciascun candidato tutte le volte che vuoi. [2, 3, 3] e [3, 2, 3] sono la stessa combinazione.

Restituisci ogni combinazione in ordine crescente e le combinazioni in ordine lessicografico: alla prima posizione in cui due combinazioni differiscono, viene prima quella con il valore più piccolo.

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 che ogni combinazione deve raggiungere esattamente
Restituisceinteger-2d-array: ogni combinazione che dà come somma il valore target, ciascuna in ordine crescente, elencata in ordine lessicografico

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, 2 + 3 + 3 e 2 + 6 fanno tutti 8, ordinati in base al loro secondo valore. Senza un 2 restano solo 3 e 6, e le loro somme sono multipli 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, e [3, 3, 5] viene prima perché il suo secondo valore, 3, è minore di 4. Nessuna combinazione di soli 4 e 5 dà 11.

Per approfondire

Ogni candidato può ora 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

La trappola è costruire due volte la stessa combinazione: 2, 3, 3 e 3, 2, 3 sono un'unica risposta. Costruisci ogni combinazione in ordine crescente, così avrà esattamente un percorso, e ordina i candidati in modo che un ramo si interrompa non appena il valore successivo è maggiore di quello che resta.

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 usa: [2, 3, 3] è un 2, due 3 e nessun 6. Prova ogni quantità per ciascun candidato ordinato, da target / c fino a 0, mantenendo le scelte che totalizzano esattamente target. Ogni combinazione ha un unico elenco di quantità, quindi non viene trovata due volte. Provare prima le quantità maggiori dà un ordine lessicografico: quando due risposte differiscono per la prima volta, quella con più copie di un valore mantiene ancora quel valore, mentre l'altra ha un valore maggiore.

Per [2, 3, 6] e target 8 ci sono 5 × 3 × 2 = 30 foglie per 3 risposte. Ogni candidato maggiore di target / 2 raddoppia il numero di foglie, quindi 40 candidati di questo tipo significano 2^40, circa 10^12.

Algoritmo

Ordina i candidati e mantieni un conteggio per ogni valore.
In choose(i, total), prova ogni conteggio k da target / nums[i] fino a 0 e chiama choose(i + 1, total + k × nums[i]).
Una volta assegnato un conteggio a ogni valore, mantieni la combinazione se total è uguale a target e riportala usando i conteggi.
Chiama choose(0, 0).

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

Procedi a ritroso in ordine crescente e pota

Intuizione

Dopo aver inserito nums[i], il valore successivo può essere di nuovo nums[i] o qualsiasi valore successivo, mai uno precedente. Una combinazione ha un solo ordine crescente, quindi ha un solo percorso, e [3, 2, 3] non viene mai costruita.

Per [2, 3, 6] ordinato e il target 8, i percorsi 2, 2, 2, 2 e 2, 3, 3 e 2, 6 raggiungono 8. Il percorso 2, 2, 3 lascia 1 e si ferma senza esaminare 6, mentre 3, 3 lascia 2, che non può essere ottenuto con nessun valore. Sono 12 chiamate contro le 30 foglie del conteggio.

A ogni livello il ciclo prova prima i valori più piccoli, quindi le risposte arrivano in ordine lessicografico. Nessuna risposta è il prefisso di un'altra, perché i valori sono positivi e raggiungono entrambi lo stesso totale.

Algoritmo

Ordina i candidati.
In backtrack(start, remaining), salva una copia del path condiviso quando remaining è 0.
Altrimenti, esegui il ciclo su i da start. Se nums[i] > remaining, interrompi: tutti i valori successivi sono maggiori.
Aggiungi nums[i], chiama backtrack(i, remaining - nums[i]), poi rimuovilo.
Chiama backtrack(0, target) e restituisci le combinazioni salvate.

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

Scorrere ogni candidato a ogni livello, invece di partire dall’indice corrente. [2, 3, 3], [3, 2, 3] e [3, 3, 2] diventano così tre risposte.
Ricorrere con i + 1 invece che con i. Ogni valore può così comparire una sola volta, quindi [2, 2, 2, 2] viene omesso.
Salvare direttamente path invece di una copia. Ogni risposta salvata è quindi la stessa lista, che il backtracking ha svuotato al termine.
Usare break con candidati che non hai ordinato. Con [6, 2, 3] e 2 ancora da raggiungere, il ciclo si interrompe a 6 e non prova mai il 2.

Domande frequenti3

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 con al massimo n scelte ciascuno: O(n^(t/m)). Lo spazio aggiuntivo è O(t/m) per il percorso e lo stack delle chiamate, oltre all'output.

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

Ricorrere con i permette al valore successivo di essere di nuovo lo stesso candidato, ed è così che un valore viene usato più di una volta. Ricorrere con i + 1 lo supera, quindi ogni candidato può essere usato al massimo una volta.

Si può risolvere Combination Sum con la programmazione dinamica?

Sì. Per ogni totale da 0 a target, conserva le combinazioni che lo raggiungono, aggiungendo un candidato alla volta, così ogni lista rimane in ordine crescente. Non esplora mai due volte un vicolo cieco, ma memorizza ogni combinazione parziale per ogni totale, il che richiede molta più memoria. Poiché l’output stesso può essere esponenziale, il backtracking è la soluzione abituale.

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

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

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