Normalmente utilizado quando se quer "testar todas as possibilidades" de alguma coisa
Às vezes pode ser bom representar as chamadas recursivas como uma árvore
Um exemplo genérico de pseudocódigo de backtracking:
backtracking(estado_atual) {
// confere alguma coisa na resposta
if (encontrou solucao)
adiciona_solucao(estado_atual)
// confere todas as possibilidades de transição
for (todas as transicoes) {
novo_estado = estado_atual + transicao // aplica a transicao
if (!valido(novo_estado)) continue;
backtracking(novo_estado)
desfaz_transicao()
}
}
Porém, cada um tem um estilo diferente
Não é relacionado exatamente com backtracking, porém pode ser útil, principalmente quando se realiza chamadas recursivas. Muitas vezes, é interessante enviar alguma variável "global" no parâmetro da função, de modo que uma alteração em alguma chamada recursiva afete todas as outras. Um exemplo básico disso é se você tiver um set<string> answer para armazenar todas as respostas possíveis.
Aprende-se em C a passagem da variável utilizando-se ponteiros:
void solve(string cur, set<string>* answer) {
...
(*answer).insert(cur); // atualizar o set de respostas
// ou answer->insert(cur);
...
}
int main() {
set<string> answer;
solve("", &answer); // passagem do endereço de answer com o &
}
Porém, é meio chato ficar tratando essas coisas de ponteiro na mão. Para isso, em C++ é possível fazer uma variável por referência, que abstrai todo esse processo de * e &:
void solve(string cur, set<string>& answer) {
...
answer.insert(cur); // efeito igual ao exemplo anterior
...
}
int main() {
set<string> answer;
solve("", answer); // passagem de answer sem utilização de nada
}
Para isso, é necessário apenas colocar tipo_variavel & nome_variavel. Também pode ser utilizada em outros contextos (não apenas chamadas recursivas).