O que é backtracking?

Question

Accepted Answer

**Backtracking** constrói soluções candidatas incrementalmente e **abandona** (retrocede) um candidato parcial assim que ele não puder levar a uma solução válida. Ele explora sistematicamente o espaço de soluções via DFS, podando becos sem saída.

## A ideia

Escolha -> explore -> desescolha. Tente uma opção, recursivamente; se falhar, desfaça e tente a próxima.

## Exemplo: todas as permutações

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## Problemas clássicos

- **N-rainhas**, Sudoku, o passeio do cavalo.
- **Subconjuntos / combinações / permutações.**
- **Busca de palavras**, resolução de labirinto.

## Complexidade

Frequentemente exponencial (p. ex., O(n!) para permutações), mas a **poda** reduz drasticamente a busca prática.

## Quando usar / armadilhas

Use para problemas de satisfação de restrições e "encontrar todas as configurações válidas". O ganho principal é a **poda antecipada** — pule branches que violam restrições. Esquecer de desfazer o estado ("desescolha") é o bug clássico.

## Por que isso importa

Backtracking é a forma sistemática de explorar espaços combinatórios sem perder ou repetir candidatos.

A boa poda transforma uma força bruta intratável em algo que termina no prazo.

Ele alimenta solvers para quebra-cabeças, agendamento e problemas de restrição em toda a indústria.