Backtracking

O que e

Backtracking e explorar uma escolha, ver no que ela da, e voltar quando aquele caminho não serve.

E um padrão de:

• escolhe
• explora
• desfaz

Quando usar

Ele aparece quando o problema pede enumerar possibilidades com restrição:

• combinações
• permutacoes
• sudoku
• caminho valido

Erro comum

O erro clássico e achar que backtracking e só recursão.

Recursão costuma ser a ferramenta.

Backtracking e a estratégia de testar e desfazer escolha.

Pergunta melhor

Antes de aplicar, vale perguntar:

1. estou testando várias possibilidades?
2. consigo descartar um caminho cedo?
3. preciso desfazer estado ao voltar?