Gere escolhas com backtracking
Monte candidatos passo a passo e desfaça escolhas para explorar todas as opções.
- Estruturar uma busca com backtracking: escolher, explorar, desfazer a escolha.
- Gerar subconjuntos, combinações e permutações.
- Podar ramos que não podem levar a uma solução.
O backtracking explora todas as soluções candidatas montando-as uma escolha de cada vez. A cada passo, você escolhe uma opção, explora mais adiante de forma recursiva e depois desfaz a escolha para testar a próxima opção. Ele resolve problemas de “gerar todos” - subconjuntos, combinações, permutações, parênteses válidos - e quebra-cabeças com restrições, como N-Rainhas e Sudoku.
O modelo de backtracking
1def backtrack(path, choices):
2 if path is complete: record a copy of path; return
3 for choice in choices:
4 if choice is invalid: continue # pruning
5 path.append(choice) # choose
6 backtrack(path, remaining) # explore
7 path.pop() # un-chooseO tamanho da saída determina a complexidade: há 2ⁿ subconjuntos e n! permutações, então esses algoritmos são exponenciais por natureza. A poda - pular escolhas que não podem dar certo - é o que os mantém viáveis.
1def subsets(nums):
2 result = []
3 path = []
4
5 def backtrack(start):
6 result.append(path[:]) # record a copy
7 for i in range(start, len(nums)):
8 path.append(nums[i])
9 backtrack(i + 1)
10 path.pop()
11
12 backtrack(0)
13 return result
14
15print(subsets([1, 2, 3]))[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Passar start adiante significa que cada elemento só é escolhido depois dos que vêm antes dele, então [1, 2] e [2, 1] não são gerados os dois. As permutações abandonam essa regra e, em vez disso, acompanham quais elementos já foram usados. Registrar path[:] (uma cópia) importa: acrescentar o próprio path guardaria o mesmo objeto de lista, que acaba vazio.
Principais conclusões
Escolher, explorar, desfazer a escolha.
Registre cópias do caminho, não o próprio caminho.
Saída exponencial significa tempo exponencial; pode cedo.
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Gere combinações
Leia n e k. Imprima todas as combinações de k números escolhidos de 1..n, uma por linha, com os números separados por espaços, em ordem lexicográfica. Use backtracking.
- Escolher 2 de 4
- Escolher 3 de 3
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…