🔙 Backtracking

The Maze Explorer Analogy

Imagine you're exploring a maze with many junctions:

1. At each junction, pick a path
2. Walk down that path until you hit a dead end or find the exit
3. If dead end, backtrack to the last junction
4. Try a different path
5. Repeat until you find the exit (or explore everything)

Backtracking is systematic trial-and-error.

You build a solution step by step. If a step leads to a dead end, you undo it ("backtrack") and try something else. With good pruning, you can avoid re-exploring many obviously-bad paths.

The Core Pattern

Every backtracking problem follows this template:

1. CHOOSE  - Make a choice from available options
2. EXPLORE - Recursively explore what happens with that choice
3. UNCHOOSE - Undo the choice (backtrack) and try something else

Think of it like a tree of decisions:

                    Start
                   /  |  \
              Choose A  B  C
               /  \
         Choose D  E
          /
      Dead End! → Backtrack to try E

Why Backtracking Works

The Brute Force Problem

Some problems have MANY possible solutions:

Permutations of [1,2,3] = 6 possibilities
Permutations of [1,2,3,4,5,6,7,8,9,10] = 3,628,800 possibilities!

Checking every possibility blindly is expensive.

The Backtracking Advantage

Backtracking prunes the search tree:

N-Queens puzzle:
  After placing Queen 1, many positions for Queen 2 become invalid
  Don't even TRY those positions!

Without pruning: Check all 64^8 = 281 trillion positions
With backtracking + pruning: you can often check far fewer positions

When you find an invalid partial solution, stop immediately. Don't waste time completing something that's already invalid.

Classic Problems Explained

1. Permutations

Problem: Generate all arrangements of n distinct numbers.

How it works:

For [1, 2, 3]:

Start: []
├── Choose 1: [1]
│   ├── Choose 2: [1,2]
│   │   └── Choose 3: [1,2,3] ✓ SOLUTION
│   │       └── Backtrack, unchoose 3
│   │   └── Backtrack, unchoose 2
│   ├── Choose 3: [1,3]
│   │   └── Choose 2: [1,3,2] ✓ SOLUTION
│   │       └── Backtrack...
...and so on

At each step, choose from remaining numbers, explore, then unchoose.

2. N-Queens

Problem: Place N queens on an NxN chessboard so none attack each other.

How it works:

Row 0: Try column 0
  │    Place Queen at (0,0)
  └─→ Row 1: Try column 0 - CONFLICT with queen above! Skip
           Try column 1 - CONFLICT on diagonal! Skip
           Try column 2 - OK, place queen at (1,2)
              └─→ Row 2: Try positions...
                   If all fail → Backtrack to Row 1

Place one queen per row. Before placing, check if it conflicts with existing queens.

3. Sudoku Solver

Problem: Fill a 9x9 grid so each row, column, and 3x3 box contains 1-9.

How it works:

Find empty cell → Try 1
  Valid? → Move to next empty cell → Try 1
    Valid? → Continue...
    Invalid? → Try 2, 3, 4...
    All fail? → BACKTRACK to previous cell, try next number

For each empty cell, try numbers 1-9. If a number causes a conflict, try the next. If all 9 fail, backtrack to the previous cell.

Backtracking vs Brute Force

Sudoku:
  Brute Force: Try all 9^81 possibilities
  Backtracking: Stop immediately when a constraint is violated

  Speed difference: Billions of times faster!

The Pruning Power

Pruning is the key to backtracking efficiency.

Without Pruning

Problem: Find subsets summing to 10 from [2, 5, 8, 12, 15]

Try: [2]        → sum=2, continue
Try: [2,5]      → sum=7, continue
Try: [2,5,8]    → sum=15, too big, but keep going anyway...
Try: [2,5,8,12] → sum=27, still going...

With Pruning

Try: [2]        → sum=2, continue
Try: [2,5]      → sum=7, continue
Try: [2,5,8]    → sum=15 > 10, STOP! Backtrack immediately.
                  Don't bother adding 12 or 15!

Common Backtracking Problems

When to Use Backtracking

Backtracking is ideal for:

1. Finding all solutions (not just one)
2. Constraint satisfaction (rules should be followed)
3. Combinatorial problems (permutations, combinations)
4. Puzzles (Sudoku, crosswords, mazes)

Not ideal for:

• Problems with overlapping subproblems (use DP instead)
• Optimization problems where greedy works

Common Mistakes

1. Forgetting to Unchoose

Wrong: Make choice → Explore → (forget to undo!)
       Choice "leaks" into other branches

Right: Make choice → Explore → UNDO choice
       Clean slate for next branch

2. Not Pruning Early

The earlier you prune, the more work you save. Check constraints BEFORE making a choice when possible.

3. Duplicates in Results

When input has duplicates, you might generate duplicate solutions. Sort input and skip same values at same level.

FAQ

Q: Backtracking vs Recursion?

Recursion is a technique (function calls itself). Backtracking is a strategy that uses recursion + undoing choices.

Q: Backtracking vs DFS?

DFS explores a graph. Backtracking explores a decision tree. Similar structure, different domains.

Q: How do I avoid duplicates?

Sort the input, then skip consecutive duplicates at the same decision level.

Q: When is backtracking too slow?

When the search space is huge and can't be pruned. For very large inputs, consider heuristics or approximations.

Q: What's the time complexity?

Usually exponential (O(n!) or O(2^n)) in the worst case, but pruning makes it much better in practice.

Summary

Backtracking systematically explores all solutions by building incrementally and abandoning invalid paths immediately.

Key Takeaways:

• Template: Choose → Explore → Unchoose
• Prune early to avoid wasted work
• Classic problems: permutations, N-Queens, Sudoku
• Better than brute force due to pruning
• Works for constraint satisfaction and combinatorial problems
• Usually exponential, but pruning makes it practical

Backtracking is your go-to for "find all valid solutions" problems!