Combination Sum

Q: Qual é a complexidade de tempo de Combination Sum?

A busca por retrocesso é exponencial. Com n candidatos, alvo t e menor candidato m , uma combinação contém no máximo t/m valores, com no máximo n opções para cada um: O(n^(t/m)) . O espaço extra é O(t/m) para o caminho e a pilha de chamadas, além da saída.

Q: Por que você faz a recursão com i e não com i + 1 em Combination Sum?

Recorrer com i permite que o próximo valor seja o mesmo candidato novamente, que é como um valor pode ser usado mais de uma vez. Recorrer com i + 1 avança além dele, então cada candidato pode ser usado no máximo uma vez.

Q: É possível resolver Combination Sum com programação dinâmica?

Sim. Para cada total de 0 a target , mantenha as combinações que chegam até ele, adicionando um candidato de cada vez para que cada lista permaneça em ordem crescente. Ele nunca explora um caminho sem saída duas vezes, mas armazena cada combinação parcial para cada total, o que consome muito mais memória. Como a própria saída pode ser exponencial, o backtracking costuma ser a resposta.

MédioBacktracking

+10

Você recebe uma lista candidates de números inteiros positivos distintos e um número inteiro positivo target. Encontre todas as combinações de candidatos cuja soma seja exatamente target, usando cada candidato quantas vezes quiser. [2, 3, 3] e [3, 2, 3] são a mesma combinação.

Retorne cada combinação em ordem crescente e as combinações em ordem lexicográfica: na primeira posição em que duas combinações diferem, aquela com o menor valor vem primeiro.

Função

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

candidatesinteger-array: os diferentes valores que você pode usar, em qualquer ordem e quantas vezes quiser
targetinteger: o total de cada combinação deve chegar exatamente
Retornainteger-2d-array: todas as combinações cuja soma seja igual ao alvo, cada uma em ordem crescente e listadas em ordem lexicográfica

Restrições

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Todos os valores em candidates são diferentes, sem uma ordem específica.
Pelo menos uma combinação alcança target, e no máximo 150 combinações o fazem.

Exemplos

Entrada: candidates = [6, 2, 3]target = 8
Saída: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Explicação: Quatro 2s, 2 + 3 + 3 e 2 + 6 resultam em 8, ordenados pelo segundo valor. Sem um 2, restam apenas 3s e 6s, e suas somas são múltiplos de 3, o que 8 não é.

Entrada: candidates = [5, 3, 4]target = 11
Saída: [[3, 3, 5], [3, 4, 4]]
Explicação: 3 + 3 + 5 e 3 + 4 + 4 somam 11, e [3, 3, 5] vem primeiro porque seu segundo valor, 3, é menor que 4. Nenhuma combinação apenas de 4s e 5s soma 11.

Para ir além

Cada candidato pode ser usado no máximo uma vez, e candidates pode conter valores repetidos. Como você altera a busca para que nenhuma combinação apareça duas vezes?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A armadilha é construir a mesma combinação duas vezes: 2, 3, 3 e 3, 2, 3 são uma única resposta. Construa cada combinação em ordem crescente, para que ela tenha exatamente um caminho, e ordene os candidatos para que um ramo pare assim que o próximo valor for maior do que o que resta.

Tente cada contagem de cada candidato

Correta, mas não termina nos maiores testes

Intuição

Uma combinação é totalmente descrita pela quantidade de cópias de cada candidato que ela usa: [2, 3, 3] é um 2, dois 3 e nenhum 6. Tente todas as quantidades para cada candidato ordenado, de target / c até 0, mantendo as escolhas cuja soma seja exatamente target. Cada combinação tem uma única lista de quantidades, então nenhuma é encontrada duas vezes. Começar pelas quantidades maiores produz uma ordem lexicográfica: quando duas respostas diferem pela primeira vez, aquela com mais cópias de um valor ainda contém esse valor, enquanto a outra contém um valor maior.

Para [2, 3, 6] e o alvo 8, há 5 × 3 × 2 = 30 folhas para 3 respostas. Cada candidato maior que target / 2 dobra a quantidade de folhas, então 40 desses candidatos significam 2^40, cerca de 10^12.

Algoritmo

Ordene os candidatos e mantenha uma contagem para cada valor.
Em choose(i, total), tente cada contagem k de target / nums[i] até 0 e chame choose(i + 1, total + k × nums[i]).
Quando cada valor tiver uma contagem, mantenha a combinação se total for igual a target e escreva-a a partir das contagens.
Chame 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

Retroceda em ordem crescente e pode

Intuição

Depois que você coloca nums[i], o próximo valor pode ser novamente nums[i] ou qualquer valor posterior, nunca um anterior. Uma combinação tem exatamente uma ordem crescente, então tem exatamente um caminho, e [3, 2, 3] nunca é construída.

Para [2, 3, 6] ordenado e alvo 8, os caminhos 2, 2, 2, 2 e 2, 3, 3 e 2, 6 chegam a 8. O caminho 2, 2, 3 deixa 1 e para sem verificar 6, e 3, 3 deixa 2, que não corresponde a nenhum valor. São 12 chamadas contra as 30 folhas da contagem.

Em cada nível, o loop tenta primeiro os valores menores, então as respostas chegam em ordem lexicográfica. Nenhuma resposta é prefixo de outra, pois os valores são positivos e ambas chegam ao mesmo total.

Algoritmo

Ordene os candidatos.
Em backtrack(start, remaining), salve uma cópia de path, que é compartilhado, quando remaining for 0.
Caso contrário, percorra i a partir de start. Se nums[i] > remaining, interrompa: todos os valores posteriores são maiores.
Adicione nums[i], chame backtrack(i, remaining - nums[i]) e, em seguida, remova-o.
Chame backtrack(0, target) e retorne as combinações salvas.

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

Armadilhas e casos extremos

Percorrer todos os candidatos em cada nível, em vez de começar pelo índice atual. [2, 3, 3], [3, 2, 3] e [3, 3, 2] são então geradas como três respostas.
Fazer a chamada recursiva com i + 1 em vez de i. Assim, cada valor pode aparecer apenas uma vez, então [2, 2, 2, 2] não é encontrado.
Salvar o próprio path em vez de uma cópia. Assim, todas as respostas salvas são a mesma lista, que o retrocesso esvazia até o final.
Usar break em candidatos que você não ordenou. Com [6, 2, 3] e 2 restantes, o loop para no 6 e nunca tenta o 2.

Perguntas frequentes3

Qual é a complexidade de tempo de Combination Sum?

A busca por retrocesso é exponencial. Com n candidatos, alvo t e menor candidato m, uma combinação contém no máximo t/m valores, com no máximo n opções para cada um: O(n^(t/m)). O espaço extra é O(t/m) para o caminho e a pilha de chamadas, além da saída.

Por que você faz a recursão com i e não com i + 1 em Combination Sum?

Recorrer com i permite que o próximo valor seja o mesmo candidato novamente, que é como um valor pode ser usado mais de uma vez. Recorrer com i + 1 avança além dele, então cada candidato pode ser usado no máximo uma vez.

É possível resolver Combination Sum com programação dinâmica?

Sim. Para cada total de 0 a target, mantenha as combinações que chegam até ele, adicionando um candidato de cada vez para que cada lista permaneça em ordem crescente. Ele nunca explora um caminho sem saída duas vezes, mas armazena cada combinação parcial para cada total, o que consome muito mais memória. Como a própria saída pode ser exponencial, o backtracking costuma ser a resposta.

def combinationSum(candidates, target):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

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