Backtracking

📋 At a Glance

Aspect	Details
Time to Read	35 minutes
Prerequisites	Part 2 (Recursion), Part 16 (DP basics)
Key Concepts	Backtracking Template, Pruning, N-Queens, Sudoku, Branch & Bound
Difficulty	⭐⭐⭐ (Intermediate)

┌─────────────────────────────────────────────────────────────────┐
│                    BACKTRACKING                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  EXPLORE → CHOOSE → EXPLORE → BACKTRACK                         │
│                                                                 │
│              ○ root                                             │
│            / | \                                                │
│           ○  ○  ○       Level 1: choices                        │
│          /|  |  |\                                              │
│         ○ ○  ×  ○ ○     Level 2: × = pruned (invalid)           │
│        /|    |    |\                                            │
│       ○ ×    ○    × ○   Level 3: leaves = solutions             │
│                                                                 │
│  Key insight: Don't explore paths that can't lead to solution   │
│                                                                 │
│  Template:                                                      │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │ backtrack(state):                                       │    │
│  │   if isComplete(state):                                 │    │
│  │     addToResults(state)                                 │    │
│  │     return                                              │    │
│  │                                                         │    │
│  │   for choice in getChoices(state):                      │    │
│  │     if isValid(choice):                                 │    │
│  │       makeChoice(choice)                                │    │
│  │       backtrack(state)                                  │    │
│  │       undoChoice(choice)  ← KEY STEP                    │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

Apply the backtracking template: Systematic approach for any problem
Solve classic problems: N-Queens, Sudoku, permutations
Prune effectively: Cut search space dramatically
Use branch and bound: Optimization with bounds
Choose between approaches: Backtracking vs DP vs brute force

🔥 Production Story: The Configuration Solver

A network equipment company needed to find valid configurations for complex hardware setups with many constraints.

The Problem

JAVA(15 lines)
Code
Loading syntax highlighter...

The Solution: Backtracking with Constraint Propagation

JAVA(48 lines)
Code
Loading syntax highlighter...

The Impact

Metric	Brute Force	Backtracking
Search space	10^50	~10^6 (pruned)
Time for solution	Impossible	0.3 seconds
Memory	N/A	O(depth)
Valid configs found	0	847

🧠 Mental Model: The Maze Explorer

┌─────────────────────────────────────────────────────────────────┐
│              BACKTRACKING AS MAZE EXPLORATION                   │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌───┬───┬───┬───┬───┐                                          │
│  │ S │   │   │ █ │   │   S = Start                              │
│  ├───┼───┼───┼───┼───┤   E = End (goal)                         │
│  │   │ █ │   │   │   │   █ = Wall (invalid)                     │
│  ├───┼───┼───┼───┼───┤   · = Path tried                         │
│  │   │   │ █ │   │   │   ○ = Current position                   │
│  ├───┼───┼───┼───┼───┤                                          │
│  │ █ │   │   │ █ │   │                                          │
│  ├───┼───┼───┼───┼───┤                                          │
│  │   │   │   │   │ E │                                          │
│  └───┴───┴───┴───┴───┘                                          │
│                                                                 │
│  Algorithm:                                                     │
│  1. From current position, try each direction                   │
│  2. If direction leads to wall or visited → skip (prune)        │
│  3. Move to new position, mark as visited                       │
│  4. If at goal → found solution!                                │
│  5. If stuck → go back (backtrack), try next direction          │
│                                                                 │
│  Key: Marking visited prevents infinite loops                   │
│       Backtracking undoes the "visited" mark                    │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🔬 Deep Dive: The Backtracking Template

General Template

JAVA(35 lines)
Code
Loading syntax highlighter...

Subsets (Power Set)

JAVA(20 lines)
Code
Loading syntax highlighter...

Permutations

JAVA(59 lines)
Code
Loading syntax highlighter...

Combinations

JAVA(51 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: N-Queens Problem

The Problem

Place N queens on an N×N chessboard so no two attack each other.

┌─────────────────────────────────────────────────────────────────┐
│                    N-QUEENS (N=4)                               │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Solution 1:          Solution 2:                               │
│  ┌───┬───┬───┬───┐    ┌───┬───┬───┬───┐                         │
│  │   │ Q │   │   │    │   │   │ Q │   │                         │
│  ├───┼───┼───┼───┤    ├───┼───┼───┼───┤                         │
│  │   │   │   │ Q │    │ Q │   │   │   │                         │
│  ├───┼───┼───┼───┤    ├───┼───┼───┼───┤                         │
│  │ Q │   │   │   │    │   │   │   │ Q │                         │
│  ├───┼───┼───┼───┤    ├───┼───┼───┼───┤                         │
│  │   │   │ Q │   │    │   │ Q │   │   │                         │
│  └───┴───┴───┴───┘    └───┴───┴───┴───┘                         │
│                                                                 │
│  Constraint: No two queens share row, column, or diagonal       │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

JAVA(84 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Sudoku Solver

Implementation

JAVA(109 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Branch and Bound

The Concept

Branch and Bound adds bounding functions to prune branches that can't improve on the best solution found so far.

┌─────────────────────────────────────────────────────────────────┐
│                 BRANCH AND BOUND                                │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Standard Backtracking:                                         │
│  - Prunes invalid solutions                                     │
│                                                                 │
│  Branch and Bound (for optimization):                           │
│  - Also prunes solutions that can't beat current best           │
│                                                                 │
│  Components:                                                    │
│  1. Branch: Split problem into subproblems                      │
│  2. Bound: Calculate optimistic estimate for subtree            │
│  3. Prune: If bound ≤ best found, skip this branch              │
│                                                                 │
│  Example for minimization:                                      │
│                                                                 │
│        Current best = 50                                        │
│              ○                                                  │
│           /  |  \                                               │
│          ○   ○   ○                                              │
│      lb=30 lb=55 lb=40                                          │
│        ↓    ✗     ↓     lb=55 > 50, prune!                      │
│      explore   explore                                          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

TSP with Branch and Bound

JAVA(84 lines)
Code
Loading syntax highlighter...

0/1 Knapsack with Branch and Bound

JAVA(70 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Forgetting to Undo Choice

JAVA(17 lines)
Code
Loading syntax highlighter...

Mistake 2: Modifying Loop Variable

JAVA(17 lines)
Code
Loading syntax highlighter...

Mistake 3: Adding Reference Instead of Copy

JAVA(17 lines)
Code
Loading syntax highlighter...

🐛 Debug This: Permutation Bug

This permutation generator has a bug. Can you find it?

JAVA(21 lines)
Code
Loading syntax highlighter...

🔍 Click to reveal the bug

Bug: Using contains(nums[i]) to check if element is used. This fails when array has duplicates!

JAVA(22 lines)
Code
Loading syntax highlighter...

Example where bug manifests:

nums = [1, 1, 2]
Bug: "1 is already in current" - skips valid permutations
Result: Missing [1,1,2], [1,2,1], [2,1,1]

💻 Exercises

Exercise 1: Generate Parentheses ⭐⭐

Generate all valid combinations of n pairs of parentheses.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 2: Letter Combinations of Phone ⭐⭐

Given digits 2-9, return all letter combinations (like phone keypad).

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 3: Word Search ⭐⭐⭐

Find if word exists in 2D grid (adjacent cells, no reuse).

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 4: Palindrome Partitioning ⭐⭐⭐

Partition string so every substring is a palindrome.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 5: Expression Add Operators ⭐⭐⭐⭐

Add +, -, * between digits to reach target.

JAVA(3 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Q1: "What's the difference between backtracking and DFS?"

Answer:

DFS is a traversal technique. Backtracking uses DFS but with:

State modification: Change state before recursing
State restoration: Undo changes after recursing
Pruning: Skip invalid branches early

JAVA(20 lines)
Code
Loading syntax highlighter...

Q2: "How do you optimize backtracking?"

Answer:

Pruning: Skip invalid branches early
```
JAVA
Code
Loading syntax highlighter...
```
Ordering: Try most constrained choice first
```
JAVA
Code
Loading syntax highlighter...
```
Constraint propagation: Reduce choices after each decision
```
JAVA
Code
Loading syntax highlighter...
```
Symmetry breaking: Avoid equivalent solutions
```
JAVA
Code
Loading syntax highlighter...
```
Memoization: Cache repeated subproblems
```
JAVA
Code
Loading syntax highlighter...
```

Q3: "When should I use backtracking vs DP?"

Answer:

Backtracking	DP
Find all solutions	Find optimal/count
Solutions have structure (permutation, subset)	Overlapping subproblems
Constraints are complex	State can be compactly represented
O(b^d) where b=branching, d=depth	Polynomial if states are polynomial

Rule of thumb:

Need all solutions → Backtracking
Need count/optimal → Try DP first
Can't define subproblems → Backtracking

Q4: "Explain the N-Queens problem and optimize it."

Answer:

JAVA(27 lines)
Code
Loading syntax highlighter...

Q5: "How does branch and bound improve over basic backtracking?"

Answer:

Branch and bound adds bounding functions for optimization problems:

Backtracking: Prune if state is INVALID
Branch & Bound: Prune if state CAN'T IMPROVE on best found

For minimization:
- Calculate lower bound on solutions in this subtree
- If lower_bound >= best_found, prune entire subtree

For maximization:
- Calculate upper bound
- If upper_bound <= best_found, prune

Example (TSP):
- Current path cost: 50
- Lower bound for remaining: 30 (sum of minimum edges)
- Total lower bound: 80
- Best complete tour found: 75
- 80 > 75 → prune this branch!

📋 Quick Reference

Problem Types

Problem	Key Insight
Subsets	Include/exclude each element
Permutations	Track used elements
Combinations	Use start index to avoid duplicates
N-Queens	Column + 2 diagonal checks
Sudoku	Row + column + box constraints

Complexity

Problem	Time	Space
Subsets	O(2^n)	O(n)
Permutations	O(n!)	O(n)
Combinations(n,k)	O(C(n,k))	O(k)
N-Queens	O(n!)	O(n)
Sudoku	O(9^(empty cells))	O(1)

Template Summary

JAVA(14 lines)
Code
Loading syntax highlighter...

🔗 What's Next?

In Part 21: Probabilistic & Approximation Algorithms, we'll explore:

Randomized algorithms
Bloom filters
HyperLogLog
Approximation algorithms

📅 Review Schedule

Day	Focus	Time
0	Full read + subsets/permutations	90 min
1	Quick Reference	10 min
3	N-Queens implementation	25 min
7	Sudoku solver	30 min
14	Debug exercise + B&B	20 min
30	Interview questions	15 min

Next: Part 21: Probabilistic & Approximation Algorithms →

Series: Algorithms Compendium Index

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Configuration Solver

The Problem

The Solution: Backtracking with Constraint Propagation

The Impact

🧠 Mental Model: The Maze Explorer

🔬 Deep Dive: The Backtracking Template

General Template

Subsets (Power Set)

Permutations

Combinations

🔬 Deep Dive: N-Queens Problem

The Problem

Implementation

🔬 Deep Dive: Sudoku Solver

Implementation

🔬 Deep Dive: Branch and Bound

The Concept

TSP with Branch and Bound

0/1 Knapsack with Branch and Bound

⚠️ Common Mistakes

Mistake 1: Forgetting to Undo Choice

Mistake 2: Modifying Loop Variable

Mistake 3: Adding Reference Instead of Copy

🐛 Debug This: Permutation Bug

💻 Exercises

Exercise 1: Generate Parentheses ⭐⭐

Exercise 2: Letter Combinations of Phone ⭐⭐

Exercise 3: Word Search ⭐⭐⭐

Exercise 4: Palindrome Partitioning ⭐⭐⭐

Exercise 5: Expression Add Operators ⭐⭐⭐⭐

🎤 Interview Questions

Q1: "What's the difference between backtracking and DFS?"

Q2: "How do you optimize backtracking?"

Q3: "When should I use backtracking vs DP?"

Q4: "Explain the N-Queens problem and optimize it."

Q5: "How does branch and bound improve over basic backtracking?"

📋 Quick Reference

Problem Types

Complexity

Template Summary

🔗 What's Next?

📅 Review Schedule

Tags: