Backtracking

Backtracking is an algorithmic technique that builds a solution incrementally, abandoning a path as soon as it determines the path cannot lead to a valid solution. Think of it as exploring a maze — you walk forward until you hit a dead end, then retrace your steps and try a different direction.

What Is Backtracking?#

Backtracking is a refined form of brute force. Instead of generating all possible solutions and then filtering, it prunes branches of the search space early by checking constraints at each step. If the current partial solution violates a constraint, the algorithm backtracks — it undoes the last choice and tries the next alternative.

Rendering diagram...

Real-World Analogies#

Solving a Sudoku: Fill in a number, check constraints, erase and try another if it fails
Navigating a Maze: Walk forward, hit a wall, go back and try a different path
Packing a Suitcase: Try placing an item, if things don't fit rearrange and try a different arrangement
Scheduling Meetings: Assign a time slot, discover a conflict, reassign to a different slot

Key Characteristics#

Property	Description
Incremental Construction	Build the solution one choice at a time
Constraint Checking	Validate each partial solution before extending it
Pruning	Abandon paths that cannot lead to valid solutions
Undo (Backtrack)	Reverse the last choice and try the next candidate
Exhaustive (with pruning)	Explores all valid paths, but skips provably dead-end branches

The Backtracking Template#

Almost every backtracking problem follows this structure:

Backtracking Template

The general pattern shared by all backtracking algorithms

Choose → Explore → Un-choose

The three steps — choose, explore, un-choose — are the backbone. Every backtracking problem is just this template with different definitions of is_solution, is_valid, and next_candidates.

Subsets#

Problem: Given a set of distinct integers, return all possible subsets (the power set).

Rendering diagram...

Every node in the decision tree is a valid subset. The key constraint: to avoid duplicates, only consider elements that come after the last chosen element.

Generate All Subsets

Find all subsets of a set using backtracking

Time:O(n × 2ⁿ)Space:O(n)Best:O(n × 2ⁿ)Worst:O(n × 2ⁿ)

Permutations#

Problem: Given a collection of distinct integers, return all possible permutations.

Unlike subsets where order doesn't matter, permutations care about arrangement: [1,2,3] and [3,2,1] are different permutations but the same subset.

Rendering diagram...

Generate All Permutations

Find all orderings of a set using backtracking

Time:O(n × n!)Space:O(n)Best:O(n × n!)Worst:O(n × n!)

N-Queens#

Problem: Place N queens on an N×N chessboard so that no two queens threaten each other. Queens can attack along rows, columns, and diagonals.

This is the classic backtracking problem — it demonstrates how pruning dramatically reduces the search space.

Rendering diagram...

Why Backtracking Excels Here#

A brute-force approach places queens in all possible positions: C(N², N) combinations. For an 8×8 board that's 4,426,165,368 combinations. Backtracking places queens row by row and prunes entire subtrees when a conflict is detected. This reduces the 8-Queens problem from billions of checks to just 15,720 — a reduction of over 99.9996%.

N-Queens

Place N queens on an N×N board with no conflicts

Time:O(n!)Space:O(n)Best:O(n!)Worst:O(n!)

Combination Sum#

Problem: Given an array of distinct integers and a target, find all unique combinations that sum to the target. Each number may be used unlimited times.

This problem elegantly shows how backtracking explores a search space while pruning branches that exceed the target.

Combination Sum

Find all combinations that sum to target, with unlimited reuse

Time:O(nᵗ/ᵐ)Space:O(t/m)Best:O(n)Worst:O(nᵗ/ᵐ)

Sudoku Solver#

Problem: Fill a 9×9 grid so that each row, column, and 3×3 box contains digits 1-9 exactly once.

Sudoku is a constraint satisfaction problem — backtracking is the natural fit because each cell placement either satisfies all constraints or must be undone.

Sudoku Solver

Fill a 9×9 Sudoku board using backtracking

Time:O(9^m)Space:O(m)Best:O(m)Worst:O(9^m)

Backtracking vs Other Approaches#

Approach	Strategy	Time Complexity	When to Use
Brute Force	Generate all, then filter	O(2ⁿ) or O(n!)	Small inputs, no structure to exploit
Backtracking	Build incrementally, prune early	O(2ⁿ) worst, much better in practice	Constraint satisfaction, combinatorial search
Dynamic Programming	Memoize overlapping subproblems	Polynomial (usually)	Optimization with overlapping subproblems
Greedy	Always pick local best	O(n) or O(n log n)	Greedy choice property holds

When Backtracking Shines#

Constraint satisfaction: Sudoku, N-Queens, crossword puzzles
Combinatorial generation: Subsets, permutations, combinations
Search problems: Word search, path finding with constraints
Optimization with constraints: When DP doesn't apply because subproblems don't overlap cleanly

Optimization Techniques#

Technique	How It Works	Example
Pruning	Skip branches that can't lead to valid solutions	Skip columns under attack in N-Queens
Ordering	Try most constrained choices first (MRV heuristic)	Fill Sudoku cell with fewest candidates first
Symmetry breaking	Eliminate equivalent search branches	First queen in N-Queens only needs to try half the columns
Memoization	Cache results of subproblems (backtracking + DP)	Combination sum with duplicate detection

Reviewing AI-Generated Code#

What to Verify#

Issue	What to Check	Common AI Mistake
Missing un-choose	Every choose has a matching undo	Forgetting path.pop() or used[i] = false
Duplicate solutions	Proper use of start index or sorting	Generating [1,2] and [2,1] as different subsets
Off-by-one in pruning	Correct inequality in constraint check	Using > instead of >= or vice versa
Copying vs referencing	Results save copies, not references	Appending path directly instead of path[:]
Base case correctness	Termination condition is right	Checking wrong length or missing return

Questions to Ask AI#

When AI generates backtracking code, verify:

"Where is the un-choose step for each choose?"
"Does this produce duplicate solutions? How are they prevented?"
"What is being pruned, and is the pruning condition correct?"
"Is the result saving a copy or a reference to the mutable path?"

Summary#

Problem	Time	Space	Key Insight
Subsets	O(n × 2ⁿ)	O(n)	Every node is a valid subset; use start index to avoid duplicates
Permutations	O(n × n!)	O(n)	Use a used-flags array; all elements considered at each level
N-Queens	O(n!)	O(n)	Place row by row; check column and diagonal conflicts
Combination Sum	O(nᵗ/ᵐ)	O(t/m)	Sort + prune; pass same index to allow reuse
Sudoku	O(9^m)	O(m)	Try digits 1-9; constraint check on row, column, and box

Key Takeaways#

Choose → Explore → Un-choose is the universal template — every backtracking problem is a variation of these three steps
Pruning is everything — the difference between backtracking and brute force is how aggressively you cut dead-end branches
Subsets use a start index, permutations use a used array — this distinction prevents duplicates while allowing different orderings
Backtracking explores, DP optimizes — use backtracking when you need all valid solutions or when subproblems don't overlap; use DP when you need the single optimal answer to overlapping subproblems
Watch for the copy bug — always append path[:] (or [...path]), never the mutable path reference itself

PreviousGreedy Algorithms

NextDynamic Programming