24 de Março
Soma de combinações
Como usar backtracking com reuso controlado para montar combinações únicas em ordem canônica.
Backtracking Intermediario 20 min TypeScript
Dado um array de inteiros distintos candidates e um inteiro target, retorne todas as combinações unicas em que os numeros escolhidos somam target.
Você pode usar o mesmo número de candidates quantas vezes quiser.
Aqui no SeniorPath:
- cada combinação deve vir em ordem não decrescente
- a lista final deve vir na ordem natural da
busca em profundidade (DFS)depois de ordenarcandidatesem ordem crescente
Exemplo:
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
O que perceber antes de codar
- O problema pede combinações unicas, não permutacoes com os mesmos valores em outra ordem.
- Reuso e permitido. Depois de escolher um número, talvez você queira escolher ele de novo.
- O indice de início controla duas coisas ao mesmo tempo: evita duplicação e define se o número atual ainda pode ser reutilizado.
Erros comuns
- reiniciar o loop do indice 0 em toda recursão e gerar a mesma combinação em várias ordens
- avancar para `i + 1` logo depois de escolher `candidates[i]` e proibir reuso sem perceber
Passo 1 - Entender o que significa "combinação unica"
O problema não quer todas as ordens possiveis.
Se [2, 2, 3] já apareceu, [2, 3, 2] e [3, 2, 2] não sao novas respostas.
Isso muda bastante o jeito de montar a busca.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- tentar cada candidato
- guardar o caminho atual
- parar quando a soma bater ou passar do alvo
Funciona.
Mas, se você sempre puder escolher qualquer candidato de novo, acaba montando as mesmas combinações em várias ordens.
Passo 3 - Perguntar como impedir essas ordens duplicadas
A ideia forte e impor uma ordem fixa.
Em vez de deixar o caminho ir e voltar entre candidatos, você decide:
- ou usa o número atual e continua do mesmo indice
- ou avanca para candidatos maiores
Assim o caminho nunca volta para tras.
Passo 4 - Transformar isso em backtracking
O estado necessário e:
startIndex: de onde o loop pode recomecarremaining: quanto ainda falta para chegar no alvopath: a combinação atual
Se remaining === 0, encontrou uma resposta.
Se remaining < 0, aquele caminho morreu.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function combinationSum(candidates: number[], target: number): number[][] {
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(number of explored paths)
Espaço: O(target / min(candidates))
Solução 1 - Gerar ordens demais e deduplicar depois
Boa versão inicial para enxergar o desperdicio.
export function combinationSum(candidates: number[], target: number): number[][] {
const unique = new Set<string>()
function dfs(remaining: number, path: number[]) {
if (remaining === 0) {
unique.add([...path].sort((a, b) => a - b).join(","))
return
}
if (remaining < 0) {
return
}
for (const candidate of candidates) {
path.push(candidate)
dfs(remaining - candidate, path)
path.pop()
}
}
dfs(target, [])
return [...unique].map((entry) => entry.split(",").map(Number))
}Ela até funciona.
Mas tem um problema feio: ela constroi o mesmo grupo de numeros em várias ordens e só limpa a bagunca no fim.
Solução 2 - Backtracking + busca em profundidade (DFS) com indice para manter ordem fixa
Agora a ideia fica mais disciplinada:
- ordene
candidates - faca
busca em profundidade (DFS)a partir de umstartIndex - no loop, só ande para frente
- quando escolher
candidates[i], recurse com o mesmoipara permitir reuso
export function combinationSum(candidates: number[], target: number): number[][] {
const sorted = [...candidates].sort((a, b) => a - b)
const result: number[][] = []
const path: number[] = []
function dfs(startIndex: number, remaining: number) {
if (remaining === 0) {
result.push([...path])
return
}
for (let index = startIndex; index < sorted.length; index += 1) {
const candidate = sorted[index]
if (candidate > remaining) {
break
}
path.push(candidate)
dfs(index, remaining - candidate)
path.pop()
}
}
dfs(0, target)
return result
}O detalhe mais importante esta aqui:
dfs(index, remaining - candidate)E index, não index + 1.
Isso permite usar o mesmo número outra vez.
Se o problema proibisse reuso, ai sim seria index + 1.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial tenta candidatos em qualquer ordem e depois precisa deduplicar respostas iguais. A versão forte ordena a entrada e usa backtracking com
startIndex. Assim eu mantenho cada combinação em ordem fixa, evito permutacoes repetidas e ainda consigo reutilizar o mesmo número quando faco a recursão com o mesmo indice.
Isso mostra quatro sinais bons:
- você entendeu por que a duplicação aparece
- você controlou a ordem em vez de limpar depois
- você soube explicar o reuso
- você conectou a regra do problema ao parametro da recursão
Quando esse padrão aparece de novo
A mesma ideia volta quando o problema pede:
- enumerar combinações
- escolher repetindo itens
- evitar respostas duplicadas por ordem diferente
- podar cedo quando o restante já não fecha
Aqui, o ganho real não e só “usar recursão”.
E perceber que uma ordem fixa simplifica o problema inteiro.