Combination Sum

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

Fazer a recursão com i permite que o próximo valor seja novamente o mesmo candidato, que é como um valor pode ser usado mais de uma vez. Fazer a recursão com i + 1 avança além dele, transformando o problema na variante em que cada candidato é usado no máximo uma vez. A outra metade da regra é igualmente importante: nunca voltar a um índice anterior a i mantém cada combinação em ordem crescente e evita duplicatas.

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 cujos valores somam exatamente target, podendo usar cada candidato quantas vezes quiser. Duas combinações são iguais quando usam os mesmos valores o mesmo número de vezes, portanto [2, 3, 3] e [3, 2, 3] contam como uma só.

Retorne cada combinação com seus valores em ordem crescente e as combinações em ordem lexicográfica: compare duas combinações valor por valor, da esquerda para a direita, e aquela com o menor valor na primeira diferença 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, quantas vezes quiser
targetinteger: o total de cada combinação deve atingir exatamente
Retornainteger-2d-array: todas as combinações cuja soma é igual ao alvo, cada uma em ordem crescente, 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 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 formam 8, assim como 2 + 3 + 3 e 2 + 6. Os três começam com 2, então o segundo valor define a ordem: 2, depois 3 e, em seguida, 6. Sem um 2, você só tem 3s e 6s, e qualquer combinação deles é múltipla 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. Eles coincidem no primeiro valor e, no segundo, o 3 é menor que o 4, então [3, 3, 5] vem primeiro. Nenhuma combinação apenas de 4s e 5s soma 11.

Entrada: candidates = [4, 9]target = 9
Saída: [[9]]
Explicação: 9 sozinho é uma combinação. Os 4 só resultam em 4, 8 e 12 ao passar por 9, e 4 + 9 já dá 13, então [9] é a única resposta.

+12 testes ocultos ao enviar

Para ir além

Cada candidato pode agora 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

Cada resposta é um multiconjunto de candidatos, e a armadilha é construir o mesmo multiconjunto mais de uma vez: escolher 2, depois 3 e depois 3 leva à mesma combinação que escolher 3, depois 2 e depois 3. A ideia que resolve isso é construir cada combinação em ordem crescente, para que haja exatamente uma maneira de construí-la, e ordenar os candidatos para que um ramo pare assim que o próximo valor for maior do que o que resta. A mesma exploração em ordem crescente fornece as combinações em ordem lexicográfica, sem precisar ordená-las no final.

Teste 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. Para [6, 2, 3] e o alvo 8, a resposta [2, 3, 3] contém um 2, dois 3s e nenhum 6. Portanto, uma maneira de encontrar todas as respostas é tentar todas as quantidades possíveis de cada candidato e manter as escolhas cujo total seja exatamente target. Um candidato c pode aparecer no máximo target / c vezes, então sua quantidade varia de 0 até esse limite.

Imagine uma árvore de decisões com um nível por candidato, após ordená-los. No nível i, você decide quantas cópias do i-ésimo valor usar, e cada folha na parte inferior representa uma escolha completa de quantidades. Cada multiconjunto tem exatamente uma lista de quantidades, então nenhuma combinação é encontrada duas vezes. Tentar primeiro a maior quantidade também produz a ordem exigida: quando duas respostas diferem pela primeira vez na quantidade de algum valor, aquela com mais cópias ainda contém esse valor pequeno, enquanto a outra já contém um valor maior, então ela vem primeiro.

O problema é o tamanho da árvore. O número de folhas é o produto de target / c + 1 para todos os candidatos: para [2, 3, 6] ordenado e alvo 8, isso resulta em 5 × 3 × 2 = 30 folhas para 3 respostas. Cada candidato maior que target / 2 dobra o número de folhas, embora possa aparecer no máximo uma vez, então só 40 desses candidatos já significam 2^40, cerca de 10^12, folhas. Os testes grandes são construídos dessa forma, e essa abordagem não consegue terminá-los.

Algoritmo

Ordene os candidatos e crie um array de contagens, uma para cada valor.
Escreva choose(i, total), que fixa a contagem do valor no índice i.
Para k de target / nums[i] até 0, defina a contagem como k e chame choose(i + 1, total + k × nums[i]).
Quando todos os valores tiverem uma contagem, mantenha a combinação se total for igual a target, escrevendo cada valor tantas vezes quanto sua contagem.
Chame choose(0, 0). As combinações mantidas já estão em ordem lexicográfica.

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

Construa cada combinação um valor de cada vez, da forma como você a escreveria: em ordem crescente. O índice inicial impõe essa ordem. Depois de colocar nums[i], o próximo valor pode ser novamente nums[i], porque um candidato pode se repetir, ou qualquer valor posterior, mas nunca um anterior. Portanto, a chamada que colocou o índice i percorre apenas os índices de i em diante. Cada combinação tem exatamente uma ordem crescente e, por isso, exatamente um caminho na árvore; assim, uma duplicata como [3, 2, 3] nunca é construída.

Aqui está a árvore inteira para [2, 3, 6] ordenado e alvo 8. A raiz tem 8 restantes e tenta 2, 3 e 6. Abaixo de 2, restam 6. Abaixo de 2, 2, restam 4, e em 2, 2, 2 restam 2; mais um 2 resulta na resposta [2, 2, 2, 2]; 2, 2, 3 deixa 1 e não leva a lugar nenhum. Abaixo de 2, 3, restam 3, e você pode tentar apenas 3 e 6; o 3 resulta em [2, 3, 3]. Abaixo de 2, 6, não resta nada: [2, 6]. Abaixo de 3, você pode tentar apenas 3 e 6, e 3, 3 deixa 2, que não completa a soma. Abaixo de 6, restam 2, e você pode tentar apenas 6. São doze chamadas ao todo, contra as 30 folhas da primeira abordagem.

A ordenação transforma um caminho sem saída em uma parada antecipada. Quando nums[i] é maior do que o valor restante, todos os valores posteriores também são maiores; assim, você sai do loop com break em vez de testar os demais. Na árvore acima, o nó 2, 2, 3 com 1 restante verifica 3, vê que não cabe e nunca verifica 6. A busca só visita prefixos cuja soma ainda é no máximo target, e é por isso que os testes grandes que fazem a primeira abordagem afundar exigem aqui apenas alguns milhares de chamadas.

A ordem das respostas vem do mesmo percurso. Em cada nível, o loop tenta primeiro os valores menores, e cada combinação é escrita em ordem crescente. Duas respostas diferem pela primeira vez no nível em que seus caminhos se separam; o caminho com o menor valor nesse nível foi explorado primeiro, então as respostas são geradas em ordem lexicográfica. Uma combinação nunca pode ser prefixo de outra, pois os valores são positivos e ambas atingem o mesmo total.

Algoritmo

Ordene os candidatos em ordem crescente.
Escreva backtrack(start, remaining) que compartilha uma lista path. Se remaining for 0, salve uma cópia de path.
Caso contrário, percorra i de start até o fim. Se nums[i] > remaining, interrompa: todos os valores seguintes são maiores.
Adicione nums[i], chame backtrack(i, remaining-nums[i]) com i, não i + 1, para que o valor possa se repetir; depois, remova-o.
Chame backtrack(0, target) e retorne as combinações salvas, já em ordem lexicográfica.

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

A maioria das respostas erradas se deve à ordem da busca, não à aritmética.

Percorrer todos os candidatos em cada nível, em vez de começar pelo índice atual, gera [2, 3, 3], [3, 2, 3] e [3, 3, 2] como três respostas. Ordenar cada resposta e remover as duplicatas depois produz a lista correta, mas dá muito mais trabalho, de forma exponencial.
Fazer a recursão com i + 1 em vez de i permite que cada valor apareça apenas uma vez, então [2, 2, 2, 2] fica faltando.
Salvar o próprio path em vez de uma cópia: assim, todas as respostas salvas são a mesma lista, que o retrocesso terá esvaziado ao 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.
Retornar as combinações na ordem sugerida pela entrada não ordenada. A lista esperada está em ordem lexicográfica, que a busca ordenada produz sem uma ordenação extra.
Em Lua e R, os arrays começam em 1, então a primeira chamada começa no índice 1 e o loop vai até o comprimento do array.

Perguntas frequentes4

Qual é a complexidade de tempo de Combination Sum?

A busca com retrocesso tem complexidade exponencial. Com n candidatos, alvo t e menor candidato m, uma combinação contém no máximo t/m valores, e cada etapa tem no máximo n opções, o que limita o trabalho a O(n^(t/m)). A poda com candidatos ordenados mantém o número real de chamadas muito abaixo desse limite, pois a busca visita apenas prefixos cuja soma ainda é no máximo t. O espaço extra é O(t/m) para o caminho atual 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?

Fazer a recursão com i permite que o próximo valor seja novamente o mesmo candidato, que é como um valor pode ser usado mais de uma vez. Fazer a recursão com i + 1 avança além dele, transformando o problema na variante em que cada candidato é usado no máximo uma vez. A outra metade da regra é igualmente importante: nunca voltar a um índice anterior a i mantém cada combinação em ordem crescente e evita duplicatas.

Como evitar combinações duplicadas sem usar um conjunto?

Gere todas as combinações em uma ordem fixa, crescente. O índice inicial impõe isso: depois de adicionar nums[i], a busca considera apenas nums[i] e os valores posteriores. Assim, cada combinação tem exatamente um caminho na árvore de busca, portanto é gerada uma única vez, sem necessidade de um conjunto ou de deduplicação final.

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

Sim. Mantenha, para cada total de 0 até o alvo, a lista de combinações que o alcançam e adicione um candidato por vez, para que os valores em cada lista permaneçam em ordem crescente, seguindo a mesma ideia de contar as maneiras de obter o troco. 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 do que o retrocesso, e talvez seja necessário ordenar a lista final. Como a própria saída pode ser exponencial, o retrocesso costuma ser a resposta.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

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