¿Qué es backtracking?

Question

Accepted Answer

**Backtracking** construye soluciones candidatas incrementalmente y **abandona** (retrocede de) un candidato parcial tan pronto como no puede llevar a una solución válida. Explora sistemáticamente el espacio de soluciones mediante DFS, podando callejones sin salida.

## La idea

Elige -> explora -> deshace la elección. Prueba una opción, recurre; si falla, deshaz y prueba la siguiente.

## Ejemplo: todas las permutaciones

```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ásicos

- **N-queens**, Sudoku, el recorrido del caballo.
- **Subconjuntos / combinaciones / permutaciones.**
- **Búsqueda de palabras**, resolución de laberintos.

## Complejidad

A menudo exponencial (p. ej., O(n!) para permutaciones), pero la **poda** reduce drásticamente la búsqueda práctica.

## Cuándo usar / trampas

Usa para problemas de satisfacción de restricciones y "busca todas las configuraciones válidas". La ventaja clave es la **poda temprana** — salta ramas que violen restricciones. Olvidar deshacer el estado ("deshacer la elección") es el error clásico.

## Por qué es importante

Backtracking es la forma sistemática de explorar espacios combinatorios sin perder ni repetir candidatos.

Una buena poda transforma un ataque de fuerza bruta intratable en algo que termina a tiempo.

Impulsa solucionadores para acertijos, programación y problemas de restricciones en toda la industria.