A árvore de decisão
Passo 1 de 8
Todo problema de backtracking é esta árvore. A raiz é o caminho vazio; cada nível escolhe mais uma letra.
A ideia
Backtracking é uma busca em profundidade (DFS) numa árvore que você nunca constrói. Cada nó é uma resposta parcial, cada aresta é uma escolha e cada folha é um candidato pronto.
O loop é sempre os mesmos três movimentos: empilhe (push) uma escolha no caminho, chame recursivamente para estendê-lo e depois desempilhe (pop). Desempilhar é todo o truque — restaura o caminho para que a próxima opção comece exatamente do mesmo estado, e é por isso que uma só lista serve à busca inteira.
Exemplo do mundo real
Testar as chaves de um molho sem etiquetas num prédio com várias portas trancadas. Você pega uma chave, avança mais fundo e, quando uma porta não abre, devolve essa chave ao molho antes de tentar a próxima — senão o molho fica errado para todas as tentativas seguintes.
O código
Sua vez
O que isto imprime?
out = []
walk(["a", "b"], [], out)
print(out)Mini quiz
1 / 3