Backtracking — Exhaustive Search Done Right¶
Backtracking is not brute force that got lucky. It’s a systematic exhaustive search with principled pruning. The difference: brute force generates all possibilities and filters after the fact. Backtracking builds candidates incrementally and abandons a branch the moment it can’t possibly lead to a valid solution — before generating anything from that branch.
The mental model: you’re walking a decision tree. At each node, you make a choice, descend deeper, and when you’ve exhausted that branch (or found what you need), you undo the choice and try the next option. That undo is the “back” in backtracking.
The Decision Tree Mental Model¶
Every backtracking problem can be framed as exploring a decision tree:
Generate all subsets of [1, 2, 3]:
[]
/ | \
[1] [2] [3]
/ \ \
[1,2] [1,3] [2,3]
/
[1,2,3]
At each level, you decide whether to include the next element. The tree has n levels, up to 2^n leaves. Backtracking explores this tree depth-first, recording valid leaves.
The key observation: you don’t need to build the entire tree. You navigate it implicitly through recursion, building the current path in a list and undoing choices on return.
The 3-Part Template¶
Every backtracking solution has the same skeleton. Memorize this:
void backtrack(/* state */) {
// BASE CASE: a complete valid solution
if (isGoalReached()) {
result.add(new ArrayList<>(current)); // snapshot — not a reference
return;
}
for (Object choice : availableChoices()) {
// 1. CHOOSE: make the choice, modify state
current.add(choice);
markUsed(choice);
// 2. EXPLORE: recurse with updated state
backtrack(/* updated state */);
// 3. UNCHOOSE: undo the choice, restore state
current.remove(current.size() - 1);
unmarkUsed(choice);
}
}
The current list tracks the partial solution being built. result accumulates completed solutions. The new ArrayList<>(current) copy when recording is mandatory — if you add current directly, all recorded solutions point to the same mutating list and you’ll end up with all-empty or all-same entries.
What most people get wrong: they modify state before the recursive call but forget to undo it after. If you’re using a mutable list or boolean array, the undo (unchoose) step is mandatory. If you’re creating a new object each call (immutable style), no undo is needed — but you pay in allocation overhead.
Pruning: The Performance Multiplier¶
Pruning is where backtracking separates from brute force. A pruning condition asks: “can any valid solution possibly extend from the current partial state?” If no, skip this branch entirely.
Without pruning (Combination Sum): generate all subsets, filter those summing to target. O(2^n × n).
With pruning: if the running sum already exceeds the target, stop. No extension of this path can succeed.
void backtrack(int[] candidates, int target, int start, int runningSum) {
if (runningSum == target) {
result.add(new ArrayList<>(current));
return;
}
if (runningSum > target) return; // PRUNING: no valid solution can extend from here
for (int i = start; i < candidates.length; i++) {
current.add(candidates[i]);
backtrack(candidates, target, i + 1, runningSum + candidates[i]);
current.remove(current.size() - 1);
}
}
If candidates are sorted, the pruning is even more powerful: once candidates[i] exceeds the remaining target, all subsequent candidates also exceed it (they’re larger), so break the loop entirely.
Canonical Problems with Full Derivations¶
1. Subsets (LC 78)¶
Generate all 2^n subsets of a set with distinct elements. Every prefix of every path through the decision tree is a valid subset.
List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current)); // record at EVERY call, not just leaves
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1);
}
}
Note: result.add(...) happens at the start of the call, not just at base cases. This records the empty set, all single-element sets, all pairs, and so on — every prefix is a valid subset.
Iterative version (understand both):
List<List<Integer>> subsetsIterative(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>()); // start: just the empty set
for (int num : nums) {
int size = result.size();
for (int i = 0; i < size; i++) {
List<Integer> newSubset = new ArrayList<>(result.get(i));
newSubset.add(num);
result.add(newSubset); // double the result size at each step
}
}
return result;
}
For each new element, every existing subset spawns a new version with the element appended. Size doubles at each iteration: 1 → 2 → 4 → 8 → … → 2^n.
2. Permutations (LC 46)¶
Generate all n! permutations of distinct integers. Unlike subsets, every element participates in every permutation — we use a used array instead of a start index.
void backtrack(int[] nums, boolean[] used) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // PRUNING: skip already chosen elements
used[i] = true;
current.add(nums[i]);
backtrack(nums, used);
current.remove(current.size() - 1);
used[i] = false;
}
}
The difference from subsets: no start index, because any unused element can appear at any position. Instead, we track which elements are currently on the path.
3. Combinations (LC 77)¶
Choose k numbers from 1 to n. Use a start index to avoid revisiting previous numbers.
void backtrack(int n, int k, int start) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
// Pruning: if remaining needed > remaining elements, no solution possible
int remaining = k - current.size();
for (int i = start; i <= n - remaining + 1; i++) { // tightened upper bound
current.add(i);
backtrack(n, k, i + 1);
current.remove(current.size() - 1);
}
}
The upper bound n - remaining + 1 is a pruning optimization: if you need remaining more elements and there are fewer than remaining elements left from i to n, skip. This reduces unnecessary branching.
4. N-Queens (LC 51)¶
Place N queens on an N×N board so no two queens share a row, column, or diagonal.
Strategy: place exactly one queen per row (row-by-row constraint eliminates row conflicts from the start). At each row, try every column. A column is valid if it’s not used by any previous queen, and neither diagonal is occupied.
void backtrack(int n, int row, int[] queenCol) {
if (row == n) {
result.add(buildBoard(queenCol, n));
return;
}
for (int col = 0; col < n; col++) {
if (!isValid(queenCol, row, col)) continue; // PRUNING
queenCol[row] = col;
backtrack(n, row + 1, queenCol);
queenCol[row] = -1;
}
}
boolean isValid(int[] queenCol, int row, int col) {
for (int r = 0; r < row; r++) {
if (queenCol[r] == col) return false; // same column
if (Math.abs(queenCol[r] - col) == row - r) return false; // same diagonal
}
return true;
}
Diagonal trick (optimized version): row - col is constant along the \ diagonal. row + col is constant along the / diagonal. Use boolean arrays indexed by these values for O(1) conflict checks instead of the O(row) loop above.
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n]; // row - col + n (offset to avoid negatives)
boolean[] diag2 = new boolean[2 * n]; // row + col
// In the loop:
if (cols[col] || diag1[row - col + n] || diag2[row + col]) continue;
cols[col] = diag1[row - col + n] = diag2[row + col] = true;
// ... recurse ...
cols[col] = diag1[row - col + n] = diag2[row + col] = false;
Time Complexity of Backtracking¶
Backtracking is inherently exponential. This is correct — problems designed for backtracking have inputs sized accordingly.
Problem |
Time Complexity |
Why |
|---|---|---|
Subsets |
O(n × 2^n) |
2^n subsets, O(n) to copy each |
Permutations |
O(n × n!) |
n! permutations, O(n) to copy |
Combinations (k of n) |
O(k × C(n,k)) |
C(n,k) solutions, O(k) to copy |
N-Queens |
O(n!) upper bound |
Pruning cuts this dramatically in practice |
For input size n ≤ 20, O(2^n) is typically acceptable. For n ≤ 12, O(n!) is typically acceptable. If the problem has larger input bounds, backtracking is not the right approach — look for DP or greedy.
How to Identify a Backtracking Problem¶
Ask these questions:
Does the problem ask to generate all X? → Almost certainly backtracking
Does it ask if any arrangement satisfies a constraint? → Backtracking with early return
Is the search space a decision tree where you make a sequence of choices? → Backtracking
Common signal phrases: “find all combinations”, “generate all permutations”, “list all solutions”, “find if any valid arrangement exists”.
The contrast: if the problem asks for the count of solutions, or the optimal solution, dynamic programming is likely more efficient. DP and backtracking solve some of the same problems, but backtracking explicitly generates solutions while DP counts or optimizes them.
Practice Problems¶
# |
Problem |
Difficulty |
Focus |
|---|---|---|---|
1 |
LC 78 — Subsets |
Easy |
Core backtracking template |
2 |
LC 77 — Combinations |
Easy |
Start index + tightened bound |
3 |
LC 46 — Permutations |
Medium |
Used array, all positions available |
4 |
LC 39 — Combination Sum |
Medium |
Element reuse + sum pruning |
5 |
LC 90 — Subsets II (with duplicates) |
Medium |
Sort + skip duplicate siblings |
6 |
LC 51 — N-Queens |
Hard |
Diagonal encoding + row-by-row |
Do 1 and 2 first. If you can write Subsets and Combinations from scratch in 20 minutes, the template is in your hands. Then Permutations — it’s the same template with a used array instead of a start index. N-Queens is the culmination: if you can implement it with the diagonal optimization in under 40 minutes, you own backtracking.
For problem 5 (Subsets II with duplicates): the key insight is sort the array first, then within a loop iteration, skip elements equal to the previous element at the same recursion level (not across levels). if (i > start && nums[i] == nums[i-1]) continue;