What is backtracking?

Question

Accepted Answer

**Backtracking** builds candidate solutions incrementally and **abandons** (backtracks from) a partial candidate as soon as it cannot lead to a valid solution. It systematically explores the solution space via DFS, pruning dead ends.

## The idea

Choose -> explore -> un-choose. Try an option, recurse; if it fails, undo it and try the next.

## Example: all permutations

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

## Classic problems

- **N-queens**, Sudoku, the knight's tour.
- **Subsets / combinations / permutations.**
- **Word search**, maze solving.

## Complexity

Often exponential (e.g., O(n!) for permutations), but **pruning** cuts the practical search dramatically.

## When to use / pitfalls

Use for constraint-satisfaction and "find all valid configurations" problems. The key win is **pruning early** — skip branches that violate constraints. Forgetting to undo state ("un-choose") is the classic bug.

## Why it matters

Backtracking is the systematic way to explore combinatorial spaces without missing or repeating candidates.

Good pruning turns an intractable brute force into something that finishes in time.

It powers solvers for puzzles, scheduling, and constraint problems across the industry.