Backtracking

Definição

Backtracking é uma técnica de busca utilizada para resolver problemas que envolvem explorar várias possibilidades, retrocedendo quando um caminho leva a uma solução inválida.

É uma abordagem baseada em tentativa e erro: testa uma opção, avança se for válida, e volta atrás (“faz backtrack”) quando encontra um impasse.

Por que usar

Ideal para problemas com múltiplas combinações ou arranjos possíveis;
Permite explorar todas as combinações possíveis (quando o algoritmo percorre todo o espaço de busca)
Útil quando não há uma fórmula direta para resolver o problema.

Exemplos clássicos

Sudoku;
Problema das N rainhas;
Geração de anagramas;
Labirintos (caminhos entre dois pontos).

Complexidade

O tempo de execução pode ser exponencial — especialmente quando o número de combinações cresce muito rápido;
Pode ser otimizado com técnicas como poda (ex: branch and bound) e heurísticas.

Exemplo prático (Python) — Todas as permutações de uma lista

def permutacoes(lista):
    resultado = []

# caminho: solução parcial em construção
# restantes: elementos ainda disponíveis para escolher
    def backtrack(caminho, restantes):
        if not restantes:
            resultado.append(caminho)
            return
        for i in range(len(restantes)):
            novo_caminho = caminho + [restantes[i]]
            nova_lista = restantes[:i] + restantes[i+1:]
            backtrack(novo_caminho, nova_lista)

    backtrack([], lista)
    return resultado

# Exemplo
itens = [1, 2, 3]
for p in permutacoes(itens):
    print(p)

Saída

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]