Recursion & Backtracking
Recursion is a function calling itself with a smaller version of the same problem. Backtracking is recursion with a purpose: systematically explore all possible solutions by making a choice, recursing, then undoing the choice (backtracking) when it leads to a dead end. If dynamic programming is "recursion without redundancy," backtracking is "brute force with early termination." It is the right tool when you need to enumerate or find all valid configurations.
This is the first technique lesson of Module 5 (Paradigms). It assumes you are comfortable with the call stack and with proofs by induction from Recursion & Mathematical Induction, and with Big-O from Complexity Analysis. By the end you will be able to write the three core templates (subsets, combinations, permutations) from memory, handle duplicate inputs without producing duplicate answers, prune a search tree in three different ways, count N-Queens solutions with bitmasks, and solve hard Sudoku puzzles in a fraction of a second.
Why this exists
Many problems have no clever formula. "List every way to split this string into palindromes." "Place 8 queens so none attack each other." "Fill this Sudoku." "Does this boolean formula have a satisfying assignment?" The only general method is to search: try a choice, see where it leads, and try something else if it fails.
The naive way to search is to generate every complete candidate and test each one. For 8 queens with one queen per row, that is boards. Backtracking builds candidates one decision at a time and checks the rules after every decision. The moment a partial candidate breaks a rule, it abandons that candidate and every completion of it at once. With that single change, 8-Queens needs only 2,057 recursive calls (measured below), not 16.7 million board checks.
The idea is old. D. H. Lehmer coined the word "backtrack" in the 1950s, and R. J. Walker described it as a general technique in 1960. Golomb and Baumert's 1965 paper "Backtrack Programming" gave the template we still use. Knuth's The Art of Computer Programming, Volume 4B (2022), spends a whole section on it. Today it runs inside SAT solvers, regex engines, package-manager resolvers and constraint solvers (see Real-world uses).
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "return all subsets / combinations / permutations" | One of the three templates below |
| "all unique …" and the input may contain repeats | Sort first, then skip equal siblings |
| "find all ways to split / partition / segment a string" | Cut-point backtracking (palindrome partitioning, word break II) |
| "place pieces so that none conflict" (queens, knights, colours) | Constraint satisfaction: one decision per row/variable, sets or bitmasks for conflicts |
| "fill the grid so every row/column/box…" | Sudoku-style search with candidate sets and MRV |
| "does a path spelling this word exist in the grid" | Grid DFS with mark-and-restore |
| "generate all valid strings" with a balance rule | Build left to right, prune on the rule (parentheses) |
| – and "all" or "any valid" | Exponential search is affordable: , |
| "count the ways" or "min/max" with overlapping subproblems | Probably DP instead; backtracking + memo = DP |
| "any assignment that satisfies these clauses" | SAT-style search: propagation + backtracking (DPLL) |
The meta-trigger: the answer is a sequence of choices, each choice has a small number of options, and you can tell early that a partial sequence is hopeless.
Recursion Fundamentals
The Call Stack
Every recursive call creates a new stack frame containing the function's local variables, parameters, and return address. The stack frames pile up until a base case is reached, then unwind as each call returns.
graph TD
subgraph "Call Stack for factorial(4)"
A["factorial(4)<br/>4 * factorial(3)"] --> B["factorial(3)<br/>3 * factorial(2)"]
B --> C["factorial(2)<br/>2 * factorial(1)"]
C --> D["factorial(1)<br/>return 1 ← base case"]
end
TypeScript:
function factorial(n: number): number {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
Python:
def factorial(n: int) -> int:
if n <= 1:
return 1 # base case
return n * factorial(n - 1) # recursive case
Anatomy of a Recursive Function
Every well-formed recursive function has:
- Base case(s): When to stop recursing. Without this, you get infinite recursion and a stack overflow.
- Recursive case(s): Break the problem into smaller subproblems and recurse.
- Progress toward base case: Each recursive call must move closer to the base case.
DANGER
Stack overflow is the #1 risk of recursion. Python has a default recursion limit of 1000. TypeScript/JavaScript depends on the engine (typically ~10,000 frames). For deep recursion, convert to iteration or increase the limit.
import sys
sys.setrecursionlimit(10000) # use with caution
Recursion vs Iteration
Every recursive algorithm can be converted to an iterative one using an explicit stack. The choice between them is about clarity and constraints:
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often clearer for tree/graph problems | Clearer for simple loops |
| Memory | stack frames where = depth | or explicit stack |
| Stack overflow risk | Yes | No |
| Performance | Function call overhead | Slightly faster |
| Tail call optimization | Some languages (not JS/Python) | N/A |
Recursion refresher
If frames, base cases or "trust the recursive call" still feel shaky, read Recursion & Mathematical Induction first. Backtracking is just recursion where each call also changes shared state on the way down and restores it on the way up.
Intuition & first principles
Decisions, partial solutions and the state-space tree
Picture packing for a trip with three items: a jacket (1), a book (2) and a camera (3). Which sets of items could you pack? You decide one item at a time. "Jacket: yes or no? Book: yes or no?" Every sequence of decisions is a path from a starting point, and the possible paths branch like a tree.
Three words are worth defining now:
- A partial solution (or partial candidate) is the list of decisions made so far, for example "jacket yes, book no".
- The state-space tree (or recursion tree) has one node per partial solution. The root is "no decisions yet". The children of a node are the partial solutions you get by making one more decision.
- A leaf is a node where no more decisions are possible. Some leaves are solutions. Some are dead ends.
Backtracking is a depth-first walk of that tree. It goes down one branch as far as it can, records any solution it meets, then climbs back up one level ("backtracks") and tries the next branch. It never builds the tree in memory. The tree exists only as the pattern of calls over time; at any moment, memory holds one root-to-node path.
Why "undo" is the heart of it
The walk keeps one shared partial solution, usually a list called path. Going down an edge appends a choice. Coming back up must remove it, so that the sibling branch starts from exactly the state its parent had. That is the choose → explore → unchoose rhythm:
- Choose: change the shared state (append to
path, mark a column as used, write a digit into a cell). - Explore: recurse to handle the rest of the decisions.
- Unchoose: reverse step 1 exactly, so the state is as it was before.
If you forget step 3, the next sibling starts from a corrupted state, and the bug is usually silent: you simply get wrong or missing answers. Sharing one list and undoing is much cheaper than copying the list at every call: per edge instead of .
Three questions for every backtracking problem
Before writing code, answer these on paper:
- What is one decision? (include element i or not; which number goes in position k; which column holds the queen in row r; where the next cut goes).
- When is a partial solution complete, and when is it a solution? (path length is k; all rows have queens; the remaining sum is 0).
- When is a partial solution hopeless? (two queens attack; the remaining sum is negative; a Sudoku cell has no legal digit). This is your pruning test, and it decides whether the search finishes in milliseconds or in years.
The Backtracking Template
Backtracking follows a consistent pattern. Memorize this template:
function backtrack(candidate, state):
if is_solution(candidate):
record(candidate)
return
for choice in get_choices(state):
if is_valid(choice, state):
make_choice(choice, state) # choose
backtrack(candidate, state) # explore
undo_choice(choice, state) # unchoose (backtrack)
graph TD
A["Start"] --> B["Make Choice 1"]
A --> C["Make Choice 2"]
A --> D["Make Choice 3"]
B --> E["Choice 1.1"]
B --> F["Choice 1.2 ✗<br/><small>pruned</small>"]
C --> G["Choice 2.1 ✓<br/><small>solution!</small>"]
C --> H["Choice 2.2"]
D --> I["Choice 3.1 ✗<br/><small>pruned</small>"]
style F fill:#f44336,color:#fff
style G fill:#4CAF50,color:#fff
style I fill:#f44336,color:#fff
The key insight: backtracking explores a decision tree. Each node represents a partial solution. Pruning cuts off entire subtrees that cannot lead to valid solutions.
The recursion tree for subsets of [1, 2, 3]
Here is the real tree that the Subsets code below walks. Each node is the current path. The edge label is the choose step; returning along the same edge is the matching unchoose. Every node is recorded as a subset, so there are exactly 8 nodes for subsets.
graph TD
R["{} start=0"] -->|"choose 1"| A["{1} start=1"]
R -->|"choose 2"| B["{2} start=2"]
R -->|"choose 3"| C["{3} start=3"]
A -->|"choose 2"| AB["{1,2} start=2"]
A -->|"choose 3"| AC["{1,3} start=3"]
AB -->|"choose 3"| ABC["{1,2,3} start=3"]
B -->|"choose 3"| BC["{2,3} start=3"]
Notice the shape: a node at index start may only choose elements at positions start or later. That is what stops {2,1} from appearing as well as {1,2}: each subset is generated once, in increasing index order.
Trace table: subsets of [1, 2, 3]
Every event the program performs, in order. "Record" happens on entering a call. Recomputed by script; it matches the order in "Try It Yourself" below.
| Step | Event | path after the event | Recorded so far |
|---|---|---|---|
| 1 | enter bt(0), record | [] | [] |
| 2 | choose 1 | [1] | |
| 3 | enter bt(1), record | [1] | [], [1] |
| 4 | choose 2 | [1,2] | |
| 5 | enter bt(2), record | [1,2] | + [1,2] |
| 6 | choose 3 | [1,2,3] | |
| 7 | enter bt(3), record; loop is empty, return | [1,2,3] | + [1,2,3] |
| 8 | unchoose 3 | [1,2] | |
| 9 | unchoose 2 | [1] | |
| 10 | choose 3 | [1,3] | |
| 11 | enter bt(3), record | [1,3] | + [1,3] |
| 12 | unchoose 3 | [1] | |
| 13 | unchoose 1 | [] | |
| 14 | choose 2 | [2] | |
| 15 | enter bt(2), record | [2] | + [2] |
| 16 | choose 3 | [2,3] | |
| 17 | enter bt(3), record | [2,3] | + [2,3] |
| 18 | unchoose 3 | [2] | |
| 19 | unchoose 2 | [] | |
| 20 | choose 3 | [3] | |
| 21 | enter bt(3), record | [3] | + [3] (8 total) |
| 22 | unchoose 3 | [] |
Count the events: 8 records (one per node), 7 chooses and 7 unchooses (one per edge, since a tree with 8 nodes has 7 edges). Every choose has a matching unchoose, and path is empty again at the end. That balance is the invariant that makes backtracking correct.
Trace table: permutations of [1, 2, 3]
The permutation template uses a used[] array instead of a start index: at every level, any unused element may come next. The first 12 events cover the whole subtree under "1 first":
| Step | Event | path | used (for 1, 2, 3) |
|---|---|---|---|
| 1 | choose 1 | [1] | T F F |
| 2 | choose 2 | [1,2] | T T F |
| 3 | choose 3 | [1,2,3] | T T T |
| 4 | full length: record [1,2,3] | [1,2,3] | T T T |
| 5 | unchoose 3 | [1,2] | T T F |
| 6 | unchoose 2 | [1] | T F F |
| 7 | choose 3 | [1,3] | T F T |
| 8 | choose 2 | [1,3,2] | T T T |
| 9 | record [1,3,2] | [1,3,2] | T T T |
| 10 | unchoose 2 | [1,3] | T F T |
| 11 | unchoose 3 | [1] | T F F |
| 12 | unchoose 1 | [] | F F F |
The same pattern repeats for "2 first" (steps 13–24) and "3 first" (steps 25–36). In total the program makes 16 calls: 1 root + 3 + 6 + 6 leaves. In general the permutation tree has nodes, which is for (16 for ).
The three templates at a glance
Almost every enumeration problem is one of three shapes. They differ only in which choices are allowed at the next level:
| Template | Next choices | Solution when | # solutions | Recursion-tree nodes |
|---|---|---|---|---|
| Subsets | indices start..n-1 (later ones only) | every node | ||
| Combinations ( of ) | indices start..n-1, with room left for the rest | len(path) == k | at most | |
| Permutations | any index not yet used | len(path) == n |
- "Order does not matter" (a set of things) → pass
start = i + 1so indices only increase. Passstart = iif an element may be reused (combination sum). - "Order matters" (an arrangement) → loop over all indices and skip used ones.
The sections below give each template in detail; all of them in four languages follow after the duplicates section.
Permutations
Generate all permutations of a set of distinct elements.
TypeScript:
function permutations(nums: number[]): number[][] {
const result: number[][] = [];
function backtrack(path: number[], remaining: Set<number>): void {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (const num of remaining) {
path.push(num);
remaining.delete(num);
backtrack(path, remaining);
path.pop(); // undo choice
remaining.add(num); // restore
}
}
backtrack([], new Set(nums));
return result;
}
Python:
def permutations(nums: list[int]) -> list[list[int]]:
result = []
def backtrack(path: list[int], remaining: set[int]) -> None:
if len(path) == len(nums):
result.append(path[:])
return
for num in list(remaining): # copy since we mutate
path.append(num)
remaining.remove(num)
backtrack(path, remaining)
path.pop()
remaining.add(num)
backtrack([], set(nums))
return result
Complexity: — there are permutations and each takes to copy.
Permutations with Duplicates
Sort the input and skip duplicate choices at the same level of the decision tree.
Python:
def permutations_unique(nums: list[int]) -> list[list[int]]:
result = []
nums.sort()
used = [False] * len(nums)
def backtrack(path: list[int]) -> None:
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# Skip duplicates: only use the first unused occurrence
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
Combinations
Choose elements from elements (order doesn't matter).
TypeScript:
function combinations(n: number, k: number): number[][] {
const result: number[][] = [];
function backtrack(start: number, path: number[]): void {
if (path.length === k) {
result.push([...path]);
return;
}
// Pruning: need (k - path.length) more elements,
// so don't start too late
for (let i = start; i <= n - (k - path.length) + 1; i++) {
path.push(i);
backtrack(i + 1, path); // i + 1 prevents reuse
path.pop();
}
}
backtrack(1, []);
return result;
}
Python:
def combinations(n: int, k: int) -> list[list[int]]:
result = []
def backtrack(start: int, path: list[int]) -> None:
if len(path) == k:
result.append(path[:])
return
# Pruning: need k - len(path) more elements
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
Complexity: — there are combinations, each taking to copy.
Combination Sum
Find all combinations that sum to a target, with elements reusable.
Python:
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
result = []
candidates.sort()
def backtrack(start: int, path: list[int], remaining: int) -> None:
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # pruning: sorted, so all subsequent are too large
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, not i+1 (reuse allowed)
path.pop()
backtrack(0, [], target)
return result
Subsets
Generate all subsets (power set). Each element is either included or excluded.
TypeScript:
function subsets(nums: number[]): number[][] {
const result: number[][] = [];
function backtrack(index: number, path: number[]): void {
result.push([...path]); // every path is a valid subset
for (let i = index; i < nums.length; i++) {
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}
Python:
def subsets(nums: list[int]) -> list[list[int]]:
result = []
def backtrack(index: int, path: list[int]) -> None:
result.append(path[:])
for i in range(index, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
Complexity: — there are subsets, each taking to copy.
Duplicates: sort, then skip equal siblings
If the input contains repeated values, the plain templates produce repeated answers. Subsets of [1, 2, 2] would list [2] twice and [1, 2] twice, because "the first 2" and "the second 2" are different indices with the same value.
The fix has two parts:
- Sort the input so equal values sit next to each other.
- In each loop, skip a value equal to the one you just tried at this same level. For subsets and combinations the test is
i > start and nums[i] == nums[i - 1].
Why i > start and not i > 0? The rule is about siblings: two children of the same node that would start with the same value produce identical subtrees. Going deeper with an equal value is fine and necessary, or [2, 2] would never appear. At i == start you are the first child at this level, so there is nothing to compare with.
graph TD
R["{} start=0"] -->|"1"| A["{1}"]
R -->|"2 (index 1)"| B["{2}"]
R -.->|"2 (index 2) skipped"| X["duplicate subtree"]
A -->|"2 (index 1)"| AB["{1,2}"]
A -.->|"2 (index 2) skipped"| Y["duplicate subtree"]
AB -->|"2 (index 2) deeper: allowed"| ABB["{1,2,2}"]
B -->|"2 (index 2) deeper: allowed"| BB["{2,2}"]
style X fill:#f44336,color:#fff
style Y fill:#f44336,color:#fff
Result: [], [1], [1,2], [1,2,2], [2], [2,2], which is 6 subsets, not 8.
For permutations the rule shown above is i > 0 and nums[i] == nums[i-1] and not used[i-1]. Read it as "equal values must be used left to right": you may only place the second 1 if the first 1 is already in the path. Each distinct arrangement then corresponds to exactly one order of using the indices. [1, 1, 2] gives 3 permutations instead of ; [1, 1, 2, 2] gives .
Sort is not optional
The skip rule compares neighbours. Without sorting, the duplicates of [2, 1, 2] are not neighbours and the rule silently fails. In TypeScript, [10, 9, 1].sort() sorts as strings and gives [1, 10, 9]; always pass (a, b) => a - b.
Combination Sum II (each element at most once, input with duplicates) combines both ideas: sort, recurse with i + 1, skip equal siblings with i > start, and break once a value exceeds the remaining target.
All templates in four languages
Subsets, subsets with duplicates, combinations, combination sum, permutations and unique permutations. Each program asserts the outputs shown in this lesson.
def subsets(nums: list[int]) -> list[list[int]]:
"""Every node of the recursion tree is a subset: record on entry."""
res: list[list[int]] = []
path: list[int] = []
def bt(start: int) -> None:
res.append(path[:]) # copy! path keeps changing
for i in range(start, len(nums)):
path.append(nums[i]) # choose
bt(i + 1) # explore (only later indices)
path.pop() # unchoose
bt(0)
return res
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
nums = sorted(nums) # equal values become neighbours
res: list[list[int]] = []
path: list[int] = []
def bt(start: int) -> None:
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # same value already tried at this depth
path.append(nums[i])
bt(i + 1)
path.pop()
bt(0)
return res
def combine(n: int, k: int) -> list[list[int]]:
res: list[list[int]] = []
path: list[int] = []
def bt(start: int) -> None:
if len(path) == k:
res.append(path[:])
return
need = k - len(path)
for i in range(start, n - need + 2): # feasibility: leave room for the rest
path.append(i)
bt(i + 1)
path.pop()
bt(1)
return res
def combination_sum(cands: list[int], target: int) -> list[list[int]]:
cands = sorted(cands)
res: list[list[int]] = []
path: list[int] = []
def bt(start: int, remaining: int) -> None:
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(cands)):
if cands[i] > remaining:
break # sorted: every later value is too big too
path.append(cands[i])
bt(i, remaining - cands[i]) # i, not i + 1: reuse allowed
path.pop()
bt(0, target)
return res
def permute(nums: list[int]) -> list[list[int]]:
res: list[list[int]] = []
path: list[int] = []
used = [False] * len(nums)
def bt() -> None:
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
bt()
path.pop()
used[i] = False
bt()
return res
def permute_unique(nums: list[int]) -> list[list[int]]:
nums = sorted(nums)
res: list[list[int]] = []
path: list[int] = []
used = [False] * len(nums)
def bt() -> None:
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue # use equal values left to right only
used[i] = True
path.append(nums[i])
bt()
path.pop()
used[i] = False
bt()
return res
if __name__ == "__main__":
assert subsets([1, 2, 3]) == [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
assert subsets_with_dup([2, 1, 2]) == [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
assert combine(4, 2) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
assert combination_sum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]
assert permute([1, 2, 3]) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
assert permute_unique([1, 1, 2]) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
assert len(subsets(list(range(10)))) == 1024
assert len(permute_unique([1, 1, 2, 2])) == 6
print("subsets:", subsets([1, 2, 3]))
print("permute_unique([1,1,2]):", permute_unique([1, 1, 2]))
print("all template checks passed")
import java.util.*;
public class Templates {
static void subsets(int[] nums, int start, Deque<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // copy: path keeps changing
for (int i = start; i < nums.length; i++) {
path.addLast(nums[i]); // choose
subsets(nums, i + 1, path, res); // explore
path.removeLast(); // unchoose
}
}
static void subsetsWithDup(int[] nums, int start, Deque<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // skip equal sibling
path.addLast(nums[i]);
subsetsWithDup(nums, i + 1, path, res);
path.removeLast();
}
}
static void combine(int n, int k, int start, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
int need = k - path.size();
for (int i = start; i <= n - need + 1; i++) { // leave room for the rest
path.addLast(i);
combine(n, k, i + 1, path, res);
path.removeLast();
}
}
static void combinationSum(int[] c, int start, int remaining, Deque<Integer> path, List<List<Integer>> res) {
if (remaining == 0) { res.add(new ArrayList<>(path)); return; }
for (int i = start; i < c.length; i++) {
if (c[i] > remaining) break; // sorted: the rest are bigger
path.addLast(c[i]);
combinationSum(c, i, remaining - c[i], path, res); // i: reuse allowed
path.removeLast();
}
}
static void permute(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; path.addLast(nums[i]);
permute(nums, used, path, res);
path.removeLast(); used[i] = false;
}
}
static void permuteUnique(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // left-to-right only
used[i] = true; path.addLast(nums[i]);
permuteUnique(nums, used, path, res);
path.removeLast(); used[i] = false;
}
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
List<List<Integer>> r = new ArrayList<>();
subsets(new int[]{1, 2, 3}, 0, new ArrayDeque<>(), r);
check(r.toString().equals("[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]"), "subsets");
int[] d = {2, 1, 2}; Arrays.sort(d);
r = new ArrayList<>(); subsetsWithDup(d, 0, new ArrayDeque<>(), r);
check(r.toString().equals("[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]"), "subsetsWithDup");
r = new ArrayList<>(); combine(4, 2, 1, new ArrayDeque<>(), r);
check(r.toString().equals("[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]"), "combine");
int[] c = {2, 3, 6, 7}; Arrays.sort(c);
r = new ArrayList<>(); combinationSum(c, 0, 7, new ArrayDeque<>(), r);
check(r.toString().equals("[[2, 2, 3], [7]]"), "combinationSum");
r = new ArrayList<>(); permute(new int[]{1, 2, 3}, new boolean[3], new ArrayDeque<>(), r);
check(r.toString().equals("[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]"), "permute");
r = new ArrayList<>(); permuteUnique(new int[]{1, 1, 2}, new boolean[3], new ArrayDeque<>(), r);
check(r.toString().equals("[[1, 1, 2], [1, 2, 1], [2, 1, 1]]"), "permuteUnique");
System.out.println("permuteUnique([1,1,2]): " + r);
System.out.println("all template checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
using VVI = vector<vector<int>>;
VVI subsets(const vector<int>& nums) {
VVI res; vector<int> path;
function<void(int)> bt = [&](int start) {
res.push_back(path); // copy: path keeps changing
for (int i = start; i < (int)nums.size(); i++) {
path.push_back(nums[i]); // choose
bt(i + 1); // explore
path.pop_back(); // unchoose
}
};
bt(0);
return res;
}
VVI subsetsWithDup(vector<int> nums) {
sort(nums.begin(), nums.end());
VVI res; vector<int> path;
function<void(int)> bt = [&](int start) {
res.push_back(path);
for (int i = start; i < (int)nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // skip equal sibling
path.push_back(nums[i]);
bt(i + 1);
path.pop_back();
}
};
bt(0);
return res;
}
VVI combine(int n, int k) {
VVI res; vector<int> path;
function<void(int)> bt = [&](int start) {
if ((int)path.size() == k) { res.push_back(path); return; }
int need = k - (int)path.size();
for (int i = start; i <= n - need + 1; i++) { // leave room for the rest
path.push_back(i);
bt(i + 1);
path.pop_back();
}
};
bt(1);
return res;
}
VVI combinationSum(vector<int> c, int target) {
sort(c.begin(), c.end());
VVI res; vector<int> path;
function<void(int, int)> bt = [&](int start, int remaining) {
if (remaining == 0) { res.push_back(path); return; }
for (int i = start; i < (int)c.size(); i++) {
if (c[i] > remaining) break; // sorted: the rest are bigger
path.push_back(c[i]);
bt(i, remaining - c[i]); // i: reuse allowed
path.pop_back();
}
};
bt(0, target);
return res;
}
VVI permute(const vector<int>& nums) {
VVI res; vector<int> path; vector<bool> used(nums.size(), false);
function<void()> bt = [&]() {
if (path.size() == nums.size()) { res.push_back(path); return; }
for (size_t i = 0; i < nums.size(); i++) {
if (used[i]) continue;
used[i] = true; path.push_back(nums[i]);
bt();
path.pop_back(); used[i] = false;
}
};
bt();
return res;
}
VVI permuteUnique(vector<int> nums) {
sort(nums.begin(), nums.end());
VVI res; vector<int> path; vector<bool> used(nums.size(), false);
function<void()> bt = [&]() {
if (path.size() == nums.size()) { res.push_back(path); return; }
for (size_t i = 0; i < nums.size(); i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // left-to-right only
used[i] = true; path.push_back(nums[i]);
bt();
path.pop_back(); used[i] = false;
}
};
bt();
return res;
}
int main() {
assert((subsets({1, 2, 3}) == VVI{{}, {1}, {1, 2}, {1, 2, 3}, {1, 3}, {2}, {2, 3}, {3}}));
assert((subsetsWithDup({2, 1, 2}) == VVI{{}, {1}, {1, 2}, {1, 2, 2}, {2}, {2, 2}}));
assert((combine(4, 2) == VVI{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}));
assert((combinationSum({2, 3, 6, 7}, 7) == VVI{{2, 2, 3}, {7}}));
assert((permute({1, 2, 3}) == VVI{{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}));
assert((permuteUnique({1, 1, 2}) == VVI{{1, 1, 2}, {1, 2, 1}, {2, 1, 1}}));
assert(subsets(vector<int>(10, 0)).size() == 1024);
cout << "all template checks passed\n";
}
function subsets(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const bt = (start: number): void => {
res.push([...path]); // copy: path keeps changing
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose
bt(i + 1); // explore
path.pop(); // unchoose
}
};
bt(0);
return res;
}
function subsetsWithDup(input: number[]): number[][] {
const nums = [...input].sort((a, b) => a - b); // numeric sort, not the default string sort
const res: number[][] = [];
const path: number[] = [];
const bt = (start: number): void => {
res.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue; // skip equal sibling
path.push(nums[i]);
bt(i + 1);
path.pop();
}
};
bt(0);
return res;
}
function combine(n: number, k: number): number[][] {
const res: number[][] = [];
const path: number[] = [];
const bt = (start: number): void => {
if (path.length === k) {
res.push([...path]);
return;
}
const need = k - path.length;
for (let i = start; i <= n - need + 1; i++) { // leave room for the rest
path.push(i);
bt(i + 1);
path.pop();
}
};
bt(1);
return res;
}
function combinationSum(input: number[], target: number): number[][] {
const c = [...input].sort((a, b) => a - b);
const res: number[][] = [];
const path: number[] = [];
const bt = (start: number, remaining: number): void => {
if (remaining === 0) {
res.push([...path]);
return;
}
for (let i = start; i < c.length; i++) {
if (c[i] > remaining) break; // sorted: the rest are bigger
path.push(c[i]);
bt(i, remaining - c[i]); // i: reuse allowed
path.pop();
}
};
bt(0, target);
return res;
}
function permute(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(nums.length).fill(false);
const bt = (): void => {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
bt();
path.pop();
used[i] = false;
}
};
bt();
return res;
}
function permuteUnique(input: number[]): number[][] {
const nums = [...input].sort((a, b) => a - b);
const res: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(nums.length).fill(false);
const bt = (): void => {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; // left-to-right only
used[i] = true;
path.push(nums[i]);
bt();
path.pop();
used[i] = false;
}
};
bt();
return res;
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
check(same(subsets([1, 2, 3]), [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]), "subsets");
check(same(subsetsWithDup([2, 1, 2]), [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]), "subsetsWithDup");
check(same(combine(4, 2), [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]), "combine");
check(same(combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]), "combinationSum");
check(same(permute([1, 2, 3]), [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]), "permute");
check(same(permuteUnique([1, 1, 2]), [[1, 1, 2], [1, 2, 1], [2, 1, 1]]), "permuteUnique");
check(subsets([10, 2, 3, 4, 5, 6, 7, 8, 9, 1]).length === 1024, "2^10");
console.log("all template checks passed");
Pruning Strategies
Pruning is what makes backtracking practical. Without pruning, backtracking degenerates into brute-force enumeration.
Types of Pruning
| Strategy | Technique | Example |
|---|---|---|
| Constraint propagation | Check constraints before recursing | N-Queens: skip attacked positions |
| Bound pruning | Compare current best with theoretical best of branch | Branch and bound optimization |
| Symmetry breaking | Avoid exploring symmetric configurations | Fix first queen to top half in N-Queens |
| Value ordering | Try most constrained choices first | Sudoku: fill cell with fewest candidates first |
| Feasibility check | Verify partial solution can still lead to a complete one | Combination sum: stop if remaining < 0 |
Pruning Example: Combination Sum with Sorting
def combination_sum_pruned(candidates: list[int], target: int) -> list[list[int]]:
result = []
candidates.sort() # sort to enable pruning
def backtrack(start: int, path: list[int], remaining: int) -> None:
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
# PRUNING: since array is sorted, all remaining candidates
# are >= candidates[i], so if this one exceeds the target,
# we can skip all of them
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return result
Most Constrained Variable (MCV)
For constraint satisfaction problems, choosing the most constrained variable first (the cell with fewest valid options in Sudoku, the most attacked row in N-Queens) dramatically reduces the search space.
The three kinds of pruning, with measured numbers
All the strategies in the table above fall into three families. Each one is a test that runs at a node and answers "can this subtree still matter?"
1. Feasibility pruning: "can this partial solution still become valid?" Cut when a rule is already broken (two queens attack) or can no longer be met (the remaining target is negative; fewer elements remain than you still need). The test must be a necessary condition: if it says "no", there must truly be no solution below. A test that is too strict silently loses answers.
Measured on Combination Sum (number of recursive calls, including calls that immediately fail):
| Input | No sort, stop only when remaining < 0 | Sorted + break when a value exceeds remaining |
|---|---|---|
[2,3,6,7], target 7 | 28 calls | 10 calls |
[2,3,5], target 8 | 23 calls | 13 calls |
The answers are identical ([[2,2,3],[7]] and [[2,2,2,2],[2,3,3],[3,5]]); only the wasted work differs. Sorting turns "this value is too big" into "this value and every value after it are too big", so one comparison cuts many siblings at once.
2. Bounding (branch and bound): "can this subtree beat the best answer found so far?" For optimisation problems, keep the best complete answer seen so far. At each node compute an optimistic bound: a value at least as good as anything in the subtree. If even the bound cannot beat the current best, cut. A tiny 0/1 knapsack (weights [5,4,6,3], values [10,40,30,50], capacity 10; best value 90) shows how much the bound's quality matters:
| Bound used | Nodes visited |
|---|---|
| none (feasibility only) | 23 |
| current value + sum of all remaining values | 17 |
| current value + fractional-knapsack bound (items sorted by value/weight) | 7 |
The fractional bound is tighter (closer to the truth), so it prunes more. The bound must never be pessimistic, or you may cut the subtree holding the real optimum. This is the same idea that makes integer-programming solvers practical; see Linear Programming.
3. Ordering: "which choice should I try first?" Ordering does not remove solutions, but it changes how early the search fails or succeeds.
- Variable ordering: decide the most constrained variable first (MRV, "minimum remaining values", also called fail-first). A cell with one legal digit costs nothing to fill; a cell with zero legal digits proves the branch dead immediately. On the hard Sudoku in the Sudoku section, MRV cuts guesses from 49,558 to 10,101.
- Value ordering: try the most promising value first (least constraining value, or the greedy choice). This helps when you need one solution or a good bound early; it does not help when you must enumerate all solutions, since every branch is visited anyway.
- Symmetry breaking: if the problem has symmetry, explore only one representative. For N-Queens, placing the first queen only in the left half of the first row and doubling the count (plus the middle column when is odd) halves the work: 1,029 calls instead of 2,057 for .
Rule of thumb
Feasibility pruning is for all solutions, bounding is for the best solution, and ordering is for any solution (or a good bound fast). Most real solvers use all three.
N-Queens
Place queens on an chessboard such that no two queens attack each other (same row, column, or diagonal).
graph TD
subgraph "4-Queens Solution"
R0["_ Q _ _"]
R1["_ _ _ Q"]
R2["Q _ _ _"]
R3["_ _ Q _"]
end
TypeScript:
function solveNQueens(n: number): string[][] {
const results: string[][] = [];
const cols = new Set<number>();
const diag1 = new Set<number>(); // row - col
const diag2 = new Set<number>(); // row + col
const board: string[][] = Array.from({ length: n }, () =>
new Array(n).fill('.')
);
function backtrack(row: number): void {
if (row === n) {
results.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
continue; // pruning: position is under attack
}
// Place queen
board[row][col] = 'Q';
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
backtrack(row + 1);
// Remove queen (backtrack)
board[row][col] = '.';
cols.delete(col);
diag1.delete(row - col);
diag2.delete(row + col);
}
}
backtrack(0);
return results;
}
Python:
def solve_n_queens(n: int) -> list[list[str]]:
results = []
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
board = [['.' ] * n for _ in range(n)]
def backtrack(row: int) -> None:
if row == n:
results.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return results
Key insight: The diagonal constraint is elegant — cells on the same diagonal share the same row - col value (one diagonal direction) or row + col value (the other direction). Using sets for columns and both diagonals gives conflict checking.
N-Queens with bitmasks
The set-based version above does three hash lookups per column per row. A faster and very compact version stores the attacked columns of the current row in three integers, one bit per column (see Bit Manipulation for the operators):
cols: bit c is set if some queen is already in column c.diag: bit c is set if a queen attacks column c along a "\" diagonal in this row.anti: bit c is set if a queen attacks column c along a "/" diagonal in this row.
The trick is how the diagonal masks move between rows. A queen at column c attacks column c + 1 one row down along "\", and column c − 1 along "/". So when you go down a row, shift diag left by one and anti right by one. Bits shifted off the board are masked away with full = (1 << n) - 1.
graph LR
A["row r: queen at column 2<br/>cols=00100 diag=00100 anti=00100"] -->|"go down one row"| B["row r+1 attacked:<br/>cols=00100 diag=01000 anti=00010"]
B -->|"free = full AND NOT (cols OR diag OR anti)"| C["free = 10001<br/>columns 0 and 4 are safe"]
(Bit strings are written with column 4 on the left and column 0 on the right; diag and anti here show only this queen's attacks.)
Two more bit tricks finish it:
free & -freeisolates the lowest set bit: the next safe column to try. In two's complement,-xflips every bit above the lowest 1, so the AND keeps only that bit.free ^= bitremoves that column from the to-do set.
Notice there is no explicit "unchoose" step. The new masks are passed by value as arguments, so the caller's masks are untouched when the call returns. Passing immutable state by value is the other way to backtrack: undo is automatic, at the price of building a new state per call. For three integers that price is zero.
Counts and the size of the search, recomputed by script:
| Solutions | Recursive calls (bitmask search) | (one queen per row, no checks) | (one per row and column) | |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 1 |
| 2 | 0 | 3 | 4 | 2 |
| 3 | 0 | 6 | 27 | 6 |
| 4 | 2 | 17 | 256 | 24 |
| 5 | 10 | 54 | 3,125 | 120 |
| 6 | 4 | 153 | 46,656 | 720 |
| 7 | 40 | 552 | 823,543 | 5,040 |
| 8 | 92 | 2,057 | 16,777,216 | 40,320 |
| 9 | 352 | 8,394 | 387,420,489 | 362,880 |
| 10 | 724 | 35,539 | 10,000,000,000 | 3,628,800 |
The solution counts match OEIS A000170. The set-based version visits exactly the same 2,057 nodes for (it applies the same test); the bitmask version is just cheaper per node. In one CPython 3 run on a laptop, took about 0.56 s with sets and 0.17 s with bitmasks, both visiting 856,189 nodes. Treat such timings as rough: they vary by machine.
def total_n_queens(n: int) -> int:
"""Count N-Queens solutions with three bitmasks (bit i = column i is attacked)."""
full = (1 << n) - 1
def place(cols: int, diag: int, anti: int) -> int:
if cols == full: # one queen in every column => n queens placed
return 1
count = 0
free = full & ~(cols | diag | anti) # columns safe in this row
while free:
bit = free & -free # lowest free column
free ^= bit # remove it from the to-do set
count += place(cols | bit,
((diag | bit) << 1) & full, # "\" attacks shift one column right
(anti | bit) >> 1) # "/" attacks shift one column left
return count
return place(0, 0, 0)
if __name__ == "__main__":
expected = [1, 0, 0, 2, 10, 4, 40, 92, 352, 724]
got = [total_n_queens(n) for n in range(1, 11)]
print("n = 1..10:", got)
assert got == expected
public class NQueens {
static int full;
// bit i set = column i is attacked in the current row
static int place(int cols, int diag, int anti) {
if (cols == full) return 1; // every column has a queen
int count = 0;
int free = full & ~(cols | diag | anti); // safe columns in this row
while (free != 0) {
int bit = free & -free; // lowest safe column
free ^= bit;
count += place(cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
}
return count;
}
static int totalNQueens(int n) {
full = (1 << n) - 1;
return place(0, 0, 0);
}
public static void main(String[] args) {
int[] expected = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724};
StringBuilder sb = new StringBuilder("n = 1..10:");
for (int n = 1; n <= 10; n++) {
int got = totalNQueens(n);
if (got != expected[n - 1]) throw new AssertionError("n=" + n + " got " + got);
sb.append(' ').append(got);
}
System.out.println(sb);
}
}
#include <cassert>
#include <cstdio>
// bit i set = column i is attacked in the current row
static int place(int full, int cols, int diag, int anti) {
if (cols == full) return 1; // every column has a queen
int count = 0;
int free = full & ~(cols | diag | anti); // safe columns in this row
while (free) {
int bit = free & -free; // lowest safe column
free ^= bit;
count += place(full, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
}
return count;
}
int totalNQueens(int n) { return place((1 << n) - 1, 0, 0, 0); }
int main() {
const int expected[] = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724};
std::printf("n = 1..10:");
for (int n = 1; n <= 10; n++) {
int got = totalNQueens(n);
assert(got == expected[n - 1]);
std::printf(" %d", got);
}
std::printf("\n");
}
function totalNQueens(n: number): number {
const full = (1 << n) - 1; // fine up to n = 30 with 32-bit bitwise ops
// bit i set = column i is attacked in the current row
const place = (cols: number, diag: number, anti: number): number => {
if (cols === full) return 1; // every column has a queen
let count = 0;
let free = full & ~(cols | diag | anti); // safe columns in this row
while (free !== 0) {
const bit = free & -free; // lowest safe column
free ^= bit;
count += place(cols | bit, ((diag | bit) << 1) & full, (anti | bit) >>> 1);
}
return count;
};
return place(0, 0, 0);
}
const expected = [1, 0, 0, 2, 10, 4, 40, 92, 352, 724];
const got: number[] = [];
for (let n = 1; n <= 10; n++) got.push(totalNQueens(n));
console.log("n = 1..10:", got.join(" "));
if (got.join() !== expected.join()) throw new Error("mismatch");
Sudoku Solver
Fill a 9x9 grid so each row, column, and 3x3 box contains digits 1-9 exactly once.
Python:
def solve_sudoku(board: list[list[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# Initialize constraints from existing numbers
for r in range(9):
for c in range(9):
if board[r][c] != '.':
num = board[r][c]
rows[r].add(num)
cols[c].add(num)
boxes[(r // 3) * 3 + c // 3].add(num)
def backtrack(r: int, c: int) -> bool:
if r == 9:
return True # all cells filled
next_r, next_c = (r, c + 1) if c < 8 else (r + 1, 0)
if board[r][c] != '.':
return backtrack(next_r, next_c)
box_idx = (r // 3) * 3 + c // 3
for num in '123456789':
if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
continue
board[r][c] = num
rows[r].add(num)
cols[c].add(num)
boxes[box_idx].add(num)
if backtrack(next_r, next_c):
return True
board[r][c] = '.'
rows[r].remove(num)
cols[c].remove(num)
boxes[box_idx].remove(num)
return False # no valid number for this cell
backtrack(0, 0)
return True
TypeScript:
function solveSudoku(board: string[][]): void {
const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set());
const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set());
const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set());
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] !== '.') {
const num = board[r][c];
rows[r].add(num);
cols[c].add(num);
boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)].add(num);
}
}
}
function backtrack(r: number, c: number): boolean {
if (r === 9) return true;
const [nr, nc] = c < 8 ? [r, c + 1] : [r + 1, 0];
if (board[r][c] !== '.') return backtrack(nr, nc);
const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);
for (let num = 1; num <= 9; num++) {
const s = String(num);
if (rows[r].has(s) || cols[c].has(s) || boxes[boxIdx].has(s)) continue;
board[r][c] = s;
rows[r].add(s);
cols[c].add(s);
boxes[boxIdx].add(s);
if (backtrack(nr, nc)) return true;
board[r][c] = '.';
rows[r].delete(s);
cols[c].delete(s);
boxes[boxIdx].delete(s);
}
return false;
}
backtrack(0, 0);
}
Correction
The Python solve_sudoku above ends with backtrack(0, 0) followed by return True, so it reports success even for an unsolvable puzzle. Return the search result instead: return backtrack(0, 0). (LeetCode's version guarantees a solution, which is why the bug is easy to miss.)
Constraint propagation and MRV
The solver above fills cells in reading order (row 0 left to right, then row 1, …) and tries digits 1 to 9. That is fine for newspaper puzzles and slow for hard ones. Two ideas from constraint programming fix most of that.
A constraint satisfaction problem (CSP) has variables (the 81 cells), domains (the digits each cell may still take) and constraints (no repeat in a row, column or box). Two terms you will meet everywhere:
- Constraint propagation: after each assignment, remove the now-illegal values from the domains of related cells (its peers: the 20 other cells in its row, column and box). Repeat while it keeps forcing things. The two classic Sudoku rules are
- naked single: a cell's domain has shrunk to one digit, so that digit must go there;
- hidden single: a digit fits in only one cell of some row, column or box, so it must go there. If any domain becomes empty, the current branch is dead.
- MRV (minimum remaining values): when you must guess, guess at the cell with the smallest domain. A 2-candidate cell has a 50% chance of guessing right; a 9-candidate cell, 11%.
The simplest form of propagation is forward checking: compute each empty cell's candidates from the row, column and box masks, and fail the branch at once if any cell has zero. The four-language solver below does exactly this plus MRV, with each domain stored as a 9-bit mask (bit d − 1 set means digit d is still allowed).
Measured on two puzzles (the LeetCode example with 51 blanks, and a 60-blank puzzle widely circulated in 2012 as "the world's hardest Sudoku", attributed to Arto Inkala). "Guesses" counts digit placements made by the search:
| Solver | LeetCode example | "Hardest" puzzle |
|---|---|---|
| Reading order, digits 1–9 (the code above) | 4,208 | 49,558 |
| MRV + forward checking, bitmasks (code below) | 51 (no wrong guess at all) | 10,101 |
| MRV + full propagation (naked and hidden singles) | 0 (solved by propagation alone) | 172 |
On the hard puzzle, full propagation cuts guesses by a factor of about 288. Note the cost per node rises too: MRV scans all 81 cells at every node. In one CPython run, the MRV version actually took longer in wall-clock time than the reading-order version on the hard puzzle (about 0.17 s against 0.07 s) despite 5 times fewer guesses. Fewer nodes is not automatically faster; measure. Peter Norvig's essay "Solving Every Sudoku Puzzle" is the classic write-up of the propagation + MRV design.
class Sudoku:
"""Bitmask Sudoku solver: MRV (fewest candidates first) + forward checking."""
def __init__(self, rows: list[str]) -> None:
self.g = [[0 if ch == "." else int(ch) for ch in r] for r in rows]
self.row = [0] * 9 # bit d-1 set = digit d used in that row
self.col = [0] * 9
self.box = [0] * 9
self.guesses = 0
for r in range(9):
for c in range(9):
if self.g[r][c]:
self._flip(r, c, 1 << (self.g[r][c] - 1))
def _flip(self, r: int, c: int, bit: int) -> None:
self.row[r] ^= bit # XOR both places and removes a digit
self.col[c] ^= bit
self.box[r // 3 * 3 + c // 3] ^= bit
def solve(self) -> bool:
best, best_count, best_cand = None, 10, 0
for r in range(9): # MRV: find the most constrained empty cell
for c in range(9):
if self.g[r][c] == 0:
cand = ~(self.row[r] | self.col[c] | self.box[r // 3 * 3 + c // 3]) & 0x1FF
k = bin(cand).count("1")
if k < best_count:
best, best_count, best_cand = (r, c), k, cand
if best is None:
return True # no empty cell left: solved
if best_count == 0:
return False # forward check: a cell has no legal digit
r, c = best
while best_cand:
bit = best_cand & -best_cand
best_cand ^= bit
self.guesses += 1
self.g[r][c] = bit.bit_length() # choose
self._flip(r, c, bit)
if self.solve(): # explore
return True
self._flip(r, c, bit) # unchoose
self.g[r][c] = 0
return False
if __name__ == "__main__":
puzzle = ["8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
"...1...3.", "..1....68", "..85...1.", ".9....4.."]
s = Sudoku(puzzle)
assert s.solve()
solved = ["".join(map(str, r)) for r in s.g]
assert solved[0] == "812753649" and solved[8] == "796318452"
for r in range(9): # every row, column and box holds 1..9
assert sorted(solved[r]) == list("123456789")
assert sorted(solved[i][r] for i in range(9)) == list("123456789")
assert sorted(solved[r // 3 * 3 + i // 3][r % 3 * 3 + i % 3] for i in range(9)) == list("123456789")
print("\n".join(solved))
print("guesses:", s.guesses)
public class Sudoku {
final int[][] g = new int[9][9];
final int[] row = new int[9], col = new int[9], box = new int[9]; // bit d-1 = digit d used
long guesses = 0;
Sudoku(String[] rows) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char ch = rows[r].charAt(c);
if (ch != '.') { g[r][c] = ch - '0'; flip(r, c, 1 << (g[r][c] - 1)); }
}
}
void flip(int r, int c, int bit) { // XOR both places and removes a digit
row[r] ^= bit; col[c] ^= bit; box[r / 3 * 3 + c / 3] ^= bit;
}
boolean solve() {
int br = -1, bc = -1, bestCount = 10, bestCand = 0;
for (int r = 0; r < 9; r++) // MRV: most constrained empty cell
for (int c = 0; c < 9; c++)
if (g[r][c] == 0) {
int cand = ~(row[r] | col[c] | box[r / 3 * 3 + c / 3]) & 0x1FF;
int k = Integer.bitCount(cand);
if (k < bestCount) { br = r; bc = c; bestCount = k; bestCand = cand; }
}
if (br < 0) return true; // solved
if (bestCount == 0) return false; // forward check failed
while (bestCand != 0) {
int bit = bestCand & -bestCand;
bestCand ^= bit;
guesses++;
g[br][bc] = Integer.numberOfTrailingZeros(bit) + 1; // choose
flip(br, bc, bit);
if (solve()) return true; // explore
flip(br, bc, bit); // unchoose
g[br][bc] = 0;
}
return false;
}
public static void main(String[] args) {
String[] puzzle = {"8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
"...1...3.", "..1....68", "..85...1.", ".9....4.."};
Sudoku s = new Sudoku(puzzle);
if (!s.solve()) throw new AssertionError("no solution");
StringBuilder sb = new StringBuilder();
for (int[] r : s.g) { for (int v : r) sb.append(v); sb.append('\n'); }
String out = sb.toString();
if (!out.startsWith("812753649") || !out.endsWith("796318452\n")) throw new AssertionError(out);
System.out.print(out);
System.out.println("guesses: " + s.guesses);
}
}
#include <array>
#include <bitset>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
struct Sudoku {
std::array<std::array<int, 9>, 9> g{};
std::array<int, 9> row{}, col{}, box{}; // bit d-1 set = digit d used
long guesses = 0;
explicit Sudoku(const std::vector<std::string>& rows) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (rows[r][c] != '.') { g[r][c] = rows[r][c] - '0'; flip(r, c, 1 << (g[r][c] - 1)); }
}
void flip(int r, int c, int bit) { // XOR both places and removes a digit
row[r] ^= bit; col[c] ^= bit; box[r / 3 * 3 + c / 3] ^= bit;
}
bool solve() {
int br = -1, bc = -1, bestCount = 10, bestCand = 0;
for (int r = 0; r < 9; r++) // MRV: most constrained empty cell
for (int c = 0; c < 9; c++)
if (g[r][c] == 0) {
int cand = ~(row[r] | col[c] | box[r / 3 * 3 + c / 3]) & 0x1FF;
int k = (int)std::bitset<9>(cand).count();
if (k < bestCount) { br = r; bc = c; bestCount = k; bestCand = cand; }
}
if (br < 0) return true; // solved
if (bestCount == 0) return false; // forward check failed
while (bestCand) {
int bit = bestCand & -bestCand;
bestCand ^= bit;
guesses++;
g[br][bc] = __builtin_ctz(bit) + 1; // choose
flip(br, bc, bit);
if (solve()) return true; // explore
flip(br, bc, bit); // unchoose
g[br][bc] = 0;
}
return false;
}
};
int main() {
Sudoku s({"8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
"...1...3.", "..1....68", "..85...1.", ".9....4.."});
bool ok = s.solve();
assert(ok);
std::string first, last;
for (int c = 0; c < 9; c++) { first += char('0' + s.g[0][c]); last += char('0' + s.g[8][c]); }
assert(first == "812753649" && last == "796318452");
for (auto& r : s.g) { for (int v : r) std::cout << v; std::cout << '\n'; }
std::cout << "guesses: " << s.guesses << '\n';
}
const popcount = (x: number): number => {
let k = 0;
for (; x !== 0; x &= x - 1) k++;
return k;
};
class Sudoku {
g: number[][];
row = new Array<number>(9).fill(0); // bit d-1 set = digit d used
col = new Array<number>(9).fill(0);
box = new Array<number>(9).fill(0);
guesses = 0;
constructor(rows: string[]) {
this.g = rows.map((r) => [...r].map((ch) => (ch === "." ? 0 : Number(ch))));
for (let r = 0; r < 9; r++)
for (let c = 0; c < 9; c++)
if (this.g[r][c] !== 0) this.flip(r, c, 1 << (this.g[r][c] - 1));
}
flip(r: number, c: number, bit: number): void {
// XOR both places and removes a digit
this.row[r] ^= bit;
this.col[c] ^= bit;
this.box[Math.floor(r / 3) * 3 + Math.floor(c / 3)] ^= bit;
}
solve(): boolean {
let br = -1, bc = -1, bestCount = 10, bestCand = 0;
for (let r = 0; r < 9; r++) // MRV: most constrained empty cell
for (let c = 0; c < 9; c++)
if (this.g[r][c] === 0) {
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
const cand = ~(this.row[r] | this.col[c] | this.box[b]) & 0x1ff;
const k = popcount(cand);
if (k < bestCount) {
br = r; bc = c; bestCount = k; bestCand = cand;
}
}
if (br < 0) return true; // solved
if (bestCount === 0) return false; // forward check failed
while (bestCand !== 0) {
const bit = bestCand & -bestCand;
bestCand ^= bit;
this.guesses++;
this.g[br][bc] = 32 - Math.clz32(bit); // choose (bit index + 1)
this.flip(br, bc, bit);
if (this.solve()) return true; // explore
this.flip(br, bc, bit); // unchoose
this.g[br][bc] = 0;
}
return false;
}
}
const s = new Sudoku(["8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
"...1...3.", "..1....68", "..85...1.", ".9....4.."]);
if (!s.solve()) throw new Error("no solution");
const out = s.g.map((r) => r.join(""));
if (out[0] !== "812753649" || out[8] !== "796318452") throw new Error("wrong solution");
console.log(out.join("\n"));
console.log("guesses:", s.guesses);
Full propagation (naked + hidden singles) in Python
Instead of undoing changes, this version copies the domain dictionary before each guess, so a failed branch is simply thrown away. Copying 81 small integers is cheap next to the work saved.
UNITS = ([[(r, c) for c in range(9)] for r in range(9)] + # rows
[[(r, c) for r in range(9)] for c in range(9)] + # columns
[[(br + i, bc + j) for i in range(3) for j in range(3)] # boxes
for br in (0, 3, 6) for bc in (0, 3, 6)])
PEERS = {(r, c): {p for u in UNITS if (r, c) in u for p in u} - {(r, c)}
for r in range(9) for c in range(9)}
def assign(dom: dict, cell: tuple, bit: int) -> bool:
"""Put digit `bit` in cell and propagate naked singles. False = contradiction."""
dom[cell] = bit
stack = [cell]
while stack:
cur = stack.pop()
for p in PEERS[cur]:
if dom[p] & dom[cur]:
dom[p] &= ~dom[cur]
if dom[p] == 0:
return False # a peer has no digit left
if dom[p] & (dom[p] - 1) == 0:
stack.append(p) # naked single: propagate it too
return True
def hidden_singles(dom: dict) -> bool:
changed = True
while changed:
changed = False
for unit in UNITS:
for d in range(9):
spots = [cell for cell in unit if dom[cell] >> d & 1]
if not spots:
return False # digit d fits nowhere in this unit
if len(spots) == 1 and dom[spots[0]] != 1 << d:
if not assign(dom, spots[0], 1 << d):
return False
changed = True
return True
def solve(rows: list[str]) -> tuple[list[str] | None, int]:
guesses = 0
dom = {(r, c): 0x1FF for r in range(9) for c in range(9)}
for r in range(9):
for c in range(9):
if rows[r][c] != "." and not assign(dom, (r, c), 1 << (int(rows[r][c]) - 1)):
return None, 0
def search(dom: dict) -> dict | None:
nonlocal guesses
if not hidden_singles(dom):
return None
open_cells = [x for x in dom if dom[x] & (dom[x] - 1)] # more than one candidate
if not open_cells:
return dom
cell = min(open_cells, key=lambda x: bin(dom[x]).count("1")) # MRV
m = dom[cell]
while m:
bit = m & -m
m ^= bit
guesses += 1
child = dict(dom) # copy = free undo
if assign(child, cell, bit):
done = search(child)
if done:
return done
return None
res = search(dom)
if res is None:
return None, guesses
return ["".join(str(res[(r, c)].bit_length()) for c in range(9)) for r in range(9)], guesses
if __name__ == "__main__":
easy = ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79"]
hard = ["8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
"...1...3.", "..1....68", "..85...1.", ".9....4.."]
grid, g = solve(easy)
assert grid[0] == "534678912" and g == 0
grid, g = solve(hard)
assert grid[0] == "812753649" and grid[8] == "796318452" and g == 172
print("easy: 0 guesses, hard:", g, "guesses")
For the general version of this idea (exact cover with Knuth's Dancing Links), see Variations.
Word Search
A classic backtracking problem: find if a word exists in a 2D grid by moving horizontally or vertically to adjacent cells.
Python:
def word_search(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def backtrack(r: int, c: int, idx: int) -> bool:
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[idx]):
return False
# Mark as visited
temp = board[r][c]
board[r][c] = '#'
found = (backtrack(r + 1, c, idx + 1) or
backtrack(r - 1, c, idx + 1) or
backtrack(r, c + 1, idx + 1) or
backtrack(r, c - 1, idx + 1))
# Restore (backtrack)
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
Word search, analysed
The code above is the same template in disguise. The decision is "which neighbour holds the next letter". The shared state is the board itself: writing '#' into a cell is the choose (mark visited), and writing the letter back is the unchoose. Forget the restore and a later start cell finds a board full of # marks: a silent wrong answer.
- Complexity: up to start cells; from each, the first step has 4 directions and every later step at most 3 (you cannot step back onto the cell you came from). So for a word of length , with recursion depth.
- Cheap pruning that matters in practice: (1) if the word has more of some letter than the board, return
falsebefore searching; (2) if the last letter of the word is rarer on the board than the first, search for the reversed word, so the search fails earlier on most starts. - Many words at once (Word Search II): walk a trie of all the words alongside the grid DFS, so one walk serves every word sharing a prefix, and delete trie leaves once found.
Palindrome Partitioning
Problem: split a string into pieces so that every piece is a palindrome (reads the same backwards), and list every such split. For "aab" the answer is [["a","a","b"], ["aa","b"]].
The decision is "where does the next piece end?" Start at index start; try every end from start to n-1; if s[start..end] is a palindrome, take it and recurse from end + 1. When start == n the whole string has been cut: record the path. Checking "is this a palindrome" from scratch costs , so precompute a table pal[i][j] once with a small DP (a substring is a palindrome when its ends match and its inside is a palindrome); then every check is .
def partition(s: str) -> list[list[str]]:
n = len(s)
# pal[i][j] is True when s[i..j] reads the same both ways (O(n^2) DP, done once)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
res: list[list[str]] = []
path: list[str] = []
def bt(start: int) -> None:
if start == n:
res.append(path[:])
return
for end in range(start, n): # decision: where does the next piece end?
if pal[start][end]: # feasibility: only palindromic pieces
path.append(s[start:end + 1])
bt(end + 1)
path.pop()
bt(0)
return res
assert partition("aab") == [["a", "a", "b"], ["aa", "b"]]
assert len(partition("aabb")) == 4
assert len(partition("aaaa")) == 8 # 2^(n-1): every cut is legal
Complexity: a string of length has gaps, and each gap is cut or not, so there are at most partitions ("aaaa" reaches all 8). Copying each costs : worst case, plus for the table. If the question is only "how few cuts?" (LeetCode 132), the answer is a DP, not a search; see Partition DP.
Generating Parentheses
Problem: list every balanced string of pairs of parentheses. For : ((())), (()()), (())(), ()(()), ()()().
Brute force writes all strings of ( and ) and keeps the balanced ones. Backtracking builds left to right and enforces two rules as it goes:
- you may add
(while fewer than have been opened; - you may add
)only whileclosed < opened, so the prefix never closes more than it opened.
Both rules are feasibility tests, and together they are exact: every prefix that obeys them can be completed to a balanced string, so the search never reaches a dead end. Every leaf is an answer.
def generate_parenthesis(n: int) -> list[str]:
res: list[str] = []
path: list[str] = []
def bt(opened: int, closed: int) -> None:
if len(path) == 2 * n:
res.append("".join(path))
return
if opened < n: # may still open a new pair
path.append("(")
bt(opened + 1, closed)
path.pop()
if closed < opened: # may close only what is open
path.append(")")
bt(opened, closed + 1)
path.pop()
bt(0, 0)
return res
assert generate_parenthesis(3) == ["((()))", "(()())", "(())()", "()(())", "()()()"]
assert [len(generate_parenthesis(n)) for n in range(1, 9)] == [1, 2, 5, 14, 42, 132, 429, 1430]
The number of answers is the Catalan number , which grows like . Measured:
| Answers | Recursive calls | Brute-force strings | |
|---|---|---|---|
| 1 | 1 | 3 | 4 |
| 2 | 2 | 8 | 16 |
| 3 | 5 | 22 | 64 |
| 4 | 14 | 64 | 256 |
| 5 | 42 | 196 | 1,024 |
| 6 | 132 | 625 | 4,096 |
| 7 | 429 | 2,055 | 16,384 |
| 8 | 1,430 | 6,917 | 65,536 |
Since every leaf is an answer and every node has a leaf below it, total work is : proportional to the size of the output. That is the best any enumeration can do, and it is the goal to aim for with pruning in general. Catalan numbers also count binary trees with nodes and triangulations of a polygon; see Combinatorics.
The ladder: enumerate everything → backtracking → pruning and bitmasks
Take 8-Queens and climb from the dumbest correct program to a fast one. Every rung gives the same answer, 92.
Rung 1: enumerate all placements, then check
Put one queen in each row (already a small insight), try all column choices, and check each full board for column and diagonal clashes in . Roughly work. Hopeless beyond .
Rung 2: enumerate permutations
Two queens in one column is never allowed, so only permutations of columns can work: boards, each checked for diagonals. . A big improvement from one observation, but it still builds every complete board before checking.
Rung 3: backtracking with a check after every queen
Place queens row by row and test the new queen against the earlier ones before going deeper. A clash in row 2 kills every completion of that prefix at once. 2,057 calls for . With sets (or boolean arrays) for columns and the two diagonal families, each test is .
Rung 4: bitmasks and symmetry
Same tree, much cheaper nodes: the free columns of a row come from one expression, and the lowest one from free & -free. Add symmetry breaking (first queen in the left half only) and the tree halves: 1,029 calls.
| Rung | Idea | Work for | Why it is better |
|---|---|---|---|
| 1. All placements | one queen per row, check at the end | 16,777,216 boards | — |
| 2. Permutations | also one per column | 40,320 boards | uses a rule to shrink the space before searching |
| 3. Backtracking | check after each queen | 2,057 calls | rejects prefixes, not boards |
| 4. Bitmasks + symmetry | same test, machine ops; half the tree | 1,029 calls | cheaper nodes, fewer nodes |
The general lesson: move every check as early as possible. Each check you can apply to a prefix instead of a full candidate removes a whole subtree.
Correctness
Why does backtracking list every solution exactly once? The proof runs on the recursion tree, by induction (exactly as in Recursion & Mathematical Induction).
Setup. Define the tree : the root is the empty partial solution; the children of a node are the extensions of that the loop allows. The program is correct if three things hold.
Claim 1 (state restoration). If bt is called with shared state equal to , it returns with the state equal to .
Proof by induction on the height of the subtree. A leaf call changes nothing. For an internal node, each loop iteration does choose (state becomes ), calls bt (which, by the induction hypothesis on the smaller subtree, returns with ), then unchoose, which exactly reverses choose and gives back . After every iteration the state is , so it is at the end. ∎
Claim 2 (each node visited exactly once). bt called at node calls itself exactly once for each child of , and by Claim 1 each child sees the correct state. By induction on height, bt(v) visits every node of the subtree of exactly once. A tree has no cycles and a unique path from the root to each node, so no node is reached twice.
Claim 3 (the tree matches the answers one-to-one). This is problem specific and is where the templates differ:
- Subsets: a node is a sequence of strictly increasing indices (the
start = i + 1rule). Every subset of has exactly one increasing ordering, so nodes and subsets are in bijection: each subset appears once. - Permutations: a leaf is a sequence of distinct indices (the
usedrule), and every permutation is exactly one such sequence. - Duplicates: among equal values, the skip rule only allows the leftmost unused copy (permutations) or the first equal sibling (subsets). So each distinct answer has exactly one canonical index sequence in the tree; all non-canonical copies are skipped.
Claim 4 (pruning is safe). A pruning test may cut node only if no solution lies in the subtree of (feasibility) or no solution there beats the best found (bounding). Under that condition, removing the subtree removes no answer that the unpruned search would have reported. If the test is merely a heuristic ("this probably will not work"), the claim fails, and so does correctness.
Claims 1–4 together give: every solution is reported, and reported exactly once.
Complexity
Count the nodes of the recursion tree and multiply by the work per node. Memory is the depth of the tree (the call stack plus the shared path), not its size, unless you store all the outputs.
| Template | Nodes | Work per node | Total time | Extra space (excluding output) |
|---|---|---|---|---|
| Subsets | to copy the path | |||
| Combinations | with the "room left" bound | copy at leaves | ||
| Permutations | loop over used | |||
| Generate parentheses | , plus at leaves | |||
| N-Queens | at most ; far fewer in practice | with bitmasks | measured: 35,539 calls at |
Two facts about these numbers:
- Output-sensitive bounds are the floor. If the answer has subsets of average size , merely writing it takes . Subsets, permutations and parentheses all meet that floor, so they are optimal for "list them all".
- Pruning changes the practical count, not the worst case. Worst-case bounds for N-Queens or Sudoku stay exponential (general Sudoku on boards is NP-complete, Yato and Seta 2003), but the measured counts above show pruning skipping more than 99.98% of the placements for 8-Queens and propagation turning a 49,558-guess search into 172 guesses. Report both: the worst case for honesty, the measured count for reality. For estimating the size of a tree you cannot afford to walk, Knuth's 1975 random-probe estimator samples random root-to-leaf paths.
Common Complexity Analysis
| Problem | Solutions | Time |
|---|---|---|
| Permutations of elements | ||
| Combinations | ||
| Subsets of elements | ||
| N-Queens | Variable (exponential) | upper bound |
| Sudoku (9x9) | 1 (unique) | worst, much less with pruning |
Backtracking vs Other Techniques
| Approach | When to Use | Time |
|---|---|---|
| Backtracking | Need ALL solutions or a specific valid configuration | Exponential (but pruning helps) |
| Dynamic Programming | Optimal value (not all solutions), overlapping subproblems | Polynomial (usually) |
| Greedy | Local optimal leads to global optimal | Polynomial |
| BFS/DFS | Graph traversal, shortest path |
TIP
If a problem asks "find the minimum/maximum" or "how many ways" — think DP first. If it asks "generate all" or "find a valid assignment" — think backtracking.
Real-world uses
- SAT solvers (DPLL and CDCL). The DPLL procedure (Davis, Putnam, Logemann, Loveland, 1960–62) decides whether a boolean formula can be made true. It is exactly this lesson: pick an unassigned variable (a decision), set it, run unit propagation (a clause with one free literal forces that literal, the SAT version of a Sudoku naked single), and backtrack on a contradiction. Modern CDCL solvers (GRASP 1996, Chaff 2001, MiniSat 2003) add clause learning and non-chronological backjumping: on a conflict they record why it happened and jump back several levels at once. These solvers verify hardware, plan schedules and resolve software dependencies with millions of variables. See also 2-SAT & Graph Coloring for the special case that needs no search.
- Regex engines. Perl, PCRE, Python's
re, Java'sjava.util.regexand JavaScript engines match patterns by backtracking: at each|,*or?they try one option and back up on failure. Features like backreferences need this. The cost is catastrophic backtracking: a pattern such as(a+)+bagainst a long string ofas explores exponentially many ways to split theas. A regex like this took down Stack Overflow for 34 minutes on 20 July 2016, and a WAF rule caused Cloudflare's global outage on 2 July 2019. Engines such as RE2, Go'sregexpand Rust'sregexsimulate an automaton instead and guarantee linear time (Russ Cox, "Regular Expression Matching Can Be Simple And Fast", 2007). Details in Regex Mastery and Regex Engines. - Constraint solvers. Gecode, Choco, MiniZinc back ends and Google OR-Tools' CP-SAT all combine propagation (shrinking domains), variable ordering heuristics like MRV, and backtracking or backjumping search, the same three ingredients as the Sudoku solver above. Timetabling, rostering and puzzle generation run on them.
- Package managers. Choosing one version of every dependency so that all constraints hold is NP-complete in general. pip's resolver (since pip 20.3, 2020) backtracks over candidate versions; Cargo documents its resolver as a backtracking search; Dart's
puband theuvinstaller use PubGrub (Natalie Weizenbaum, 2018), a CDCL-style algorithm with conflict learning. - Parsers and logic programming. Recursive-descent parsers try one grammar alternative and fall back to the next on failure. Packrat parsing (Bryan Ford, 2002) memoises those attempts to guarantee linear time for PEGs, and CPython has used a PEG parser since 3.9 (PEP 617). Prolog runs every program as a depth-first search with chronological backtracking.
- Exact cover. Sudoku, polyomino tilings and N-Queens are all exact-cover problems; Knuth's Algorithm X with "Dancing Links" (2000) is a backtracking search with an undo-friendly linked-list representation.
Pitfalls & edge cases
- Forgetting to undo. Every mutation in choose needs its exact inverse in unchoose, in reverse order, on every path out of the loop body, including early
continueorreturn. If you returnTrueearly (Sudoku, word search) it is fine to skip the undo, but only if no caller needs the state restored. - Recording a reference instead of a copy.
res.append(path)stores the same list object every time; at the end every entry is the empty list. Usepath[:],[...path],new ArrayList<>(path), or C++'sres.push_back(path)(which copies). - Mutable default arguments in Python.
def bt(path=[])creates one list when the function is defined and reuses it across calls, so a second top-level call starts with leftovers. Usepath=Noneand create the list inside, or a closure as in this lesson. - Sharing vs copying, decided on purpose. Copy-on-call (pass
path + [x]) needs no undo but costs per call; shared-with-undo costs . Both are correct. Mixing them by accident (copying some state, sharing other state) is the classic bug. - Modifying a collection while iterating it. The original Python permutations iterates
list(remaining)for exactly this reason; iterating the live set while removing from it raises an error. - Duplicate skip with
i > 0instead ofi > start(subsets/combinations): this also blocks going deeper with an equal value, so[2, 2]disappears. - Wrong base case placement. In subsets, record at every node. In permutations and combinations, only at full length. Recording at the wrong place gives too many or too few answers.
- Edge cases: empty input (subsets returns
[[]], one answer, not zero); or in combinations; N-Queens for has zero solutions; a target of 0 in combination sum returns[[]]. - Recursion depth. Depth equals the number of decisions: 81 for Sudoku, for permutations, the word length in word search. Python's limit of 1000 is usually enough, but grid flood-style backtracking over 10⁶ cells is not; use an explicit stack.
- Exponential output. subsets is about a million lists, roughly 10 million integers. Check the expected output size against memory before you start.
Variations
- Find one vs find all vs count vs best. Return
Trueup the stack on the first solution (Sudoku); collect all (subsets); return counts instead of lists (N-Queens II, no copying); keep a running best with bounding (branch and bound). - Iterative backtracking with an explicit stack of (state, next-choice index) frames: same tree, no recursion limit. See Converting recursion to iteration.
- Bitmask enumeration instead of recursion for subsets:
for mask in range(1 << n). Simple, but cannot prune. Gosper's hack steps through all -bit masks for combinations. - Next-permutation (lexicographic successor,
std::next_permutation) lists permutations without recursion and handles duplicates for free. - Memoised backtracking = DP. If the future of a partial solution depends only on a small summary (index, remaining sum), cache by that summary. Word Break II, "count the ways" and Bitmask DP grow from here.
- Meet in the middle. Split items in half, enumerate choices per half, and combine with sorting or hashing: subset sum for goes from to about per half.
- Exact cover with Dancing Links (Knuth's Algorithm X): always branch on the column with fewest candidates (MRV again), with undo via relinked list nodes.
- Backjumping and learning (CDCL): on failure jump to the decision that actually caused it and store a clause so the same conflict never repeats.
- Randomised restarts and local search for huge instances where a complete search is hopeless: see Heuristics & Metaheuristics.
Practice ladder
Each problem is described in my own words; follow the link for the full statement. Easy to hard.
1. Subsets (LeetCode 78) — List every subset of distinct numbers. The subsets template, verbatim.
Hint
Record at every node; loop i from start; recurse with i + 1.
2. Permutations (LeetCode 46) — List every ordering of distinct numbers.
Hint
used[] array; record at length . Alternative: swap nums[k] with each nums[i] for i >= k, recurse on k + 1, swap back.
3. Combinations (LeetCode 77) — Every way to choose numbers from 1 to .
Hint
Stop the loop at n - (k - len(path)) + 1: past that, not enough numbers remain.
4. Creating Strings (CSES 1622) — Print every distinct rearrangement of a short string, in sorted order, with its count. Letters may repeat.
Hint
Sort the letters, then the duplicate-skipping permutation template outputs distinct strings already in sorted order. Or count letters and branch on "which letter next" while counts remain.
5. Generate Parentheses (LeetCode 22) — Every balanced string with pairs.
Hint
Open while opened < n; close while closed < opened. No dead ends. The code in this lesson is a full solution.
6. Subsets II (LeetCode 90) — Subsets when the input may repeat values; no duplicate subsets.
Hint
Sort; skip nums[i] == nums[i-1] when i > start. The code in the templates section is a full solution.
7. Permutations II (LeetCode 47) — Distinct orderings of a list with repeats.
Hint
Sort; skip when the equal left neighbour is unused (not used[i-1]).
8. Combination Sum (LeetCode 39) — Pick numbers (reuse allowed) that add to a target.
Hint
Recurse with i (not i + 1); sort and break when a value exceeds the remainder.
9. Combination Sum II (LeetCode 40) — Same, but each element used at most once and the input has repeats.
Solution
Sort; recurse with i + 1; skip equal siblings; break when too big.
def combination_sum2(cands, target):
cands = sorted(cands)
res, path = [], []
def bt(start, remaining):
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(cands)):
if i > start and cands[i] == cands[i - 1]:
continue # equal sibling: same subtree again
if cands[i] > remaining:
break
path.append(cands[i])
bt(i + 1, remaining - cands[i]) # i + 1: each element once
path.pop()
bt(0, target)
return res
assert combination_sum2([10, 1, 2, 7, 6, 1, 5], 8) == [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
10. Palindrome Partitioning (LeetCode 131) — Every split of a string into palindromic pieces.
Hint
Decide where the next piece ends; precompute pal[i][j]. The code in this lesson is a full solution.
11. Word Search (LeetCode 79) — Does the word appear as a path of adjacent cells, each used once?
Hint
Mark with #, recurse into 4 neighbours, restore. Prune with letter counts and by reversing the word if its last letter is rarer.
12. Chessboard and Queens (CSES 1624) — Count ways to place 8 queens on an 8×8 board where some squares are reserved.
Solution
N-Queens with one extra feasibility test: a reserved square is never free. With bitmasks, precompute a "blocked" mask per row and AND it out.
def count_queens(board): # board: 8 strings of '.' (free) and '*' (reserved)
n, full = 8, (1 << 8) - 1
blocked = [sum(1 << c for c in range(n) if row[c] == "*") for row in board]
def place(r, cols, diag, anti):
if r == n:
return 1
free = full & ~(cols | diag | anti | blocked[r])
total = 0
while free:
bit = free & -free
free ^= bit
total += place(r + 1, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1)
return total
return place(0, 0, 0, 0)
assert count_queens(["........"] * 8) == 92
sample = ["........", "........", "..*.....", "........", "........", ".....**.", "...*....", "........"]
assert count_queens(sample) == 65
13. N-Queens II (LeetCode 52) and N-Queens (LeetCode 51) — Count the solutions; then print the boards.
Hint
The bitmask counter in this lesson solves 52 directly. For 51, also keep the chosen column per row and build strings at the leaves.
14. Sudoku Solver (LeetCode 37) — Fill a 9×9 board in place.
Hint
Row/column/box bitmasks plus MRV. The four-language solver in this lesson is a full solution after converting the board format.
15. Word Search II (LeetCode 212) — Find every word from a dictionary that appears in the grid.
Solution
Build a trie of the words. Run one grid DFS per start cell, walking the trie in step with the grid; a trie node marked "end of word" yields an answer. Remove a word's end marker once found so it is reported once, and prune trie branches that become empty.
def find_words(board, words):
trie = {}
for w in words:
node = trie
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # end-of-word marker holds the word
R, C, found = len(board), len(board[0]), []
def dfs(r, c, parent):
ch = board[r][c]
node = parent[ch]
if "$" in node:
found.append(node.pop("$")) # report once
board[r][c] = "#" # choose: mark visited
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
dfs(nr, nc, node)
board[r][c] = ch # unchoose: restore
if not node:
parent.pop(ch) # prune exhausted trie branch
for r in range(R):
for c in range(C):
if board[r][c] in trie:
dfs(r, c, trie)
return found
grid = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
assert sorted(find_words(grid, ["oath", "pea", "eat", "rain"])) == ["eat", "oath"]
Practice Problems
| Problem | Pattern | Difficulty |
|---|---|---|
| Subsets | Subset generation | Medium |
| Permutations | Permutation generation | Medium |
| Combinations | Combination generation | Medium |
| Combination Sum | Combination + pruning | Medium |
| Letter Combinations of Phone Number | Multi-way branching | Medium |
| Palindrome Partitioning | String partition + palindrome check | Medium |
| Generate Parentheses | Constraint: open >= close | Medium |
| Word Search | Grid backtracking | Medium |
| N-Queens | Constraint satisfaction | Hard |
| Sudoku Solver | Constraint satisfaction | Hard |
| Word Search II | Trie + backtracking | Hard |
| Expression Add Operators | String partition + evaluation | Hard |
Common mistakes & interview follow-ups
"What is the time complexity of your subsets / permutations solution?" Count nodes times work per node: and . Say that this matches the output size, so no algorithm that lists them all can do asymptotically better.
"Your input now has duplicates." Sort, then skip equal siblings (i > start) for subsets and combinations, or require left-to-right use of equal values (not used[i-1]) for permutations. Explain why the rule is about siblings, not depth.
"Can you do it without recursion?" Subsets: iterate masks 0 .. 2^n - 1, or start from [[]] and for each element append it to every existing subset. Permutations: repeated next-permutation. General backtracking: an explicit stack of frames.
"Only count the N-Queens solutions; make it fast." Bitmasks, no board, no copying, plus left-half symmetry. Mention that the counts are known only up to (computed in 2016 with massive parallel search), which shows how fast the tree grows.
"Return just one Sudoku solution as fast as possible." Bitmask domains, MRV, propagation (naked and hidden singles), and stop at the first solution. Mention that a pure CSP framing generalises (Dancing Links for exact cover, or hand it to a SAT/CP solver).
"Your regex service timed out on one input. Why?" Catastrophic backtracking: nested quantifiers like (a+)+ give exponentially many ways to match. Fixes: rewrite the pattern to be unambiguous, use atomic groups or possessive quantifiers, set a match timeout, or switch to an automaton engine such as RE2.
"When would you choose DP over backtracking here?" When the question asks for a count or an optimum and partial solutions with the same summary (index, remaining sum) have the same future. Then memoise on that summary.
Mistakes interviewers watch for: appending path without copying; forgetting to undo one of several state changes; i > 0 instead of i > start in the duplicate rule; not sorting before deduplication; recording subsets only at the leaves; looping to n instead of n - need + 1 in combinations (correct, but they will ask about pruning); using a default mutable argument in Python.
Try It Yourself
Problem 1: Generate all permutations of [1, 2, 3].
Solution
Using the backtracking template (choose, explore, unchoose):
- Start with path=[], remaining={1,2,3}
- Choose 1: path=[1], remaining={2,3}
- Choose 2: path=[1,2], remaining={3} → [1,2,3]
- Choose 3: path=[1,3], remaining={2} → [1,3,2]
- Choose 2: path=[2], remaining={1,3}
- Choose 1: [2,1,3]
- Choose 3: [2,3,1]
- Choose 3: path=[3], remaining={1,2}
- Choose 1: [3,1,2]
- Choose 2: [3,2,1] Answer: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] (6 permutations = 3!)
Problem 2: Generate all subsets of [1, 2, 3].
Solution
At each element, decide to include or exclude:
- [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] Using the iterative backtracking approach:
- Start: index=0, path=[] → record []
- Add 1: path=[1] → record [1]. Add 2: [1,2] → record. Add 3: [1,2,3] → record. Pop 3. Pop 2.
- Add 3: [1,3] → record. Pop 3. Pop 1.
- Add 2: [2] → record. Add 3: [2,3] → record. Pop 3. Pop 2.
- Add 3: [3] → record. Pop 3. Answer: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] (8 subsets = )
Problem 3: Solve the 4-Queens problem: place 4 queens on a 4x4 board so no two attack each other.
Solution
Place queens row by row, tracking occupied columns and diagonals:
- Row 0: try col 0 → blocked later. Try col 1 → works.
- Row 1: try col 3 → works (col 3 free, diags 1-3=-2 and 1+3=4 free).
- Row 2: try col 0 → works (col 0 free, diags 2-0=2 and 2+0=2 free).
- Row 3: try col 2 → works (col 2 free, diags 3-2=1 and 3+2=5 free). Solution:
. Q . .
. . . Q
Q . . .
. . Q .
There are 2 solutions for 4-Queens.
Problem 4: Find all combinations of [2, 3, 6, 7] that sum to 7 (elements can be reused).
Solution
Using backtracking with pruning (sort first: [2, 3, 6, 7]):
- Start with 2: remaining=5. Pick 2 again: remaining=3. Pick 2: remaining=1. Pick 2: remaining=-1 → prune. Pick 3: remaining=-2 → prune. Backtrack.
- Path [2,2]: remaining=3. Pick 3: remaining=0 → [2,2,3] found.
- Path [2]: remaining=5. Pick 3: remaining=2. Pick 3: remaining=-1 → prune. Backtrack.
- Path [3]: remaining=4. Pick 3: remaining=1. No valid picks → prune. Backtrack.
- Path [7]: remaining=0 → [7] found. Answer: [[2,2,3], [7]]
Problem 5: Use backtracking to check if the word "ABCCED" exists in the grid:
A B C E
S F C S
A D E E
Solution
Start from each cell matching 'A':
- Cell (0,0)='A' → (0,1)='B' → (1,1)='F'? No. → (0,0) not adjacent to 'B' except (0,1). Try (0,1)='B' → (0,2)='C' → (1,2)='C' → (2,2)='E' → (2,1)='D' → found! Path: (0,0)A → (0,1)B → (0,2)C → (1,2)C → (2,2)E → (2,1)D Answer: true -- the word exists in the grid.
Quick Quiz
1. What is the time complexity of generating all subsets of a set with elements?
- a)
- b)
- c)
- d)
Answer
c) — There are subsets, and each takes to copy into the result list.
2. What is the key difference between backtracking and brute force?
- a) Backtracking is always faster
- b) Backtracking prunes branches that cannot lead to valid solutions, avoiding unnecessary exploration
- c) Brute force cannot solve constraint satisfaction problems
- d) Backtracking uses more memory
Answer
b) Backtracking prunes branches that cannot lead to valid solutions, avoiding unnecessary exploration — Backtracking is brute force with early termination. When a partial solution violates constraints, the entire subtree is skipped.
3. In the N-Queens problem, how do you check diagonal conflicts in ?
- a) Check all previously placed queens
- b) Use sets tracking
row - colandrow + colvalues - c) Use a 2D boolean array for the board
- d) Compare absolute differences of coordinates
Answer
b) Use sets tracking row - col and row + col values — All cells on the same diagonal share the same row - col value (for one diagonal direction) or row + col value (for the other). Storing these in sets gives conflict checking.
4. When should you use backtracking instead of dynamic programming?
- a) When you need the optimal value only
- b) When you need to generate all valid solutions or find a specific valid configuration
- c) When the problem has overlapping subproblems
- d) When the input size is very large
Answer
b) When you need to generate all valid solutions or find a specific valid configuration — DP finds optimal values efficiently but does not enumerate all solutions. Backtracking systematically explores all possibilities and is the right tool when you need to list or count all valid configurations.
5. Why is sorting the input often the first step in backtracking problems?
- a) It makes the recursion faster
- b) It enables pruning (skip remaining candidates when current exceeds target) and duplicate avoidance
- c) It reduces memory usage
- d) It is required by the backtracking template
Answer
b) It enables pruning (skip remaining candidates when current exceeds target) and duplicate avoidance — With sorted input, once a candidate exceeds the remaining budget you can break (all subsequent candidates are larger). Sorting also groups duplicates together, making it easy to skip duplicate branches.
6. In the subsets trace for [1, 2, 3], how many choose events are there, and why?
Answer
- The recursion tree has 8 nodes (one per subset), and a tree with 8 nodes has 7 edges. Each edge is walked down once (choose) and up once (unchoose).
7. Why does the bitmask N-Queens code need no explicit "unchoose"?
Answer
The new masks are passed as arguments (by value). The caller's cols, diag and anti never change, so returning from the call restores the state automatically.
8. A Sudoku cell has candidates {4, 7}; another has {1, 2, 5, 8, 9}. Under MRV, which do you branch on, and why?
Answer
The {4, 7} cell. It has the fewest remaining values, so a guess there is right half the time, and if both values fail the branch dies after only two tries. This is the "fail-first" principle.
Further Reading
- Dynamic Programming — when backtracking has overlapping subproblems, add memoization
- Trees — tree traversals are recursion in action
- Graphs — DFS is backtracking on graphs
- Arrays & Strings — many string problems use backtracking for generation
- Recursion & Mathematical Induction — the Module 0 lesson this one builds on
- Bit Manipulation — the operators behind the N-Queens and Sudoku masks
- Tries — the data structure behind Word Search II
- Regex Mastery — where backtracking shows up (and blows up) in everyday code
Sources
- Donald E. Knuth, The Art of Computer Programming, Volume 4B (2022), §7.2.2 "Backtrack programming" (including Dancing Links and the estimation of tree sizes).
- Solomon W. Golomb and Leonard D. Baumert, "Backtrack Programming", Journal of the ACM 12(4), 1965. R. J. Walker, "An enumerative technique for a class of combinatorial problems", Proc. Symposia in Applied Mathematics 10, 1960.
- Donald E. Knuth, "Estimating the efficiency of backtrack programs", Mathematics of Computation 29, 1975; and "Dancing Links", 2000, arXiv:cs/0011047.
- Steven S. Skiena, The Algorithm Design Manual, 3rd ed. (2020), Chapter 9 "Combinatorial Search".
- Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th ed. — Chapter 6 "Constraint Satisfaction Problems" (MRV, forward checking, propagation).
- Peter Norvig, "Solving Every Sudoku Puzzle".
- Martin Davis, George Logemann and Donald Loveland, "A machine program for theorem-proving", Communications of the ACM 5(7), 1962; João Marques-Silva and Karem Sakallah, "GRASP: A Search Algorithm for Propositional Satisfiability", IEEE Transactions on Computers 48(5), 1999.
- Russ Cox, "Regular Expression Matching Can Be Simple And Fast", 2007. Stack Overflow status blog, "Outage Postmortem – July 20, 2016". Cloudflare, "Details of the Cloudflare outage on July 2, 2019".
- Takayuki Yato and Takahiro Seta, "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles", IEICE Transactions E86-A(5), 2003 (Sudoku is NP-complete).
- OEIS A000170 (number of N-Queens solutions) and A000108 (Catalan numbers).
- cp-algorithms, Generating all K-combinations.
Lessons: previous — Paradigms overview · next — Divide & Conquer · module — Paradigms · course — DSA: Zero to Mastery.
Related Archon pages: Recursion & Mathematical Induction · Complexity Analysis · DFS · 2-SAT & Graph Coloring · Greedy Algorithms · Bit Manipulation · Tries · Bitmask DP · Partition DP.