Backtracking
Systematically explore every choice, undo it, and try the next. Subsets, permutations, combinations, constraint puzzles, and the pruning that makes them fast enough.
The idea
Backtracking builds a solution one choice at a time. After making a choice, recurse to make the next one. When you return, undo the choice and try the next option. It's a depth-first search over a tree of partial solutions (the state space tree).
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
|
[1,2,3]
The universal template
def backtrack(state, choices):
if is_complete(state):
results.append(copy_of(state)) # COPY — state will keep changing
return
for choice in choices_available(state):
if not valid(choice, state):
continue # prune
make(choice, state) # 1. choose
backtrack(state, choices) # 2. explore
undo(choice, state) # 3. un-choose
void backtrack(State& state) {
if (isComplete(state)) { results.push_back(state.path); return; }
for (auto& choice : choicesAvailable(state)) {
if (!valid(choice, state)) continue;
make(choice, state);
backtrack(state);
undo(choice, state);
}
}
Three questions define every backtracking problem:
- What's the path/state? (current subset, current permutation, board)
- What are the choices at this step? (next element to add, digit to place)
- When is it complete, and when can I prune?
Subsets (the power set)
Each element is either in or out → 2ⁿ subsets. The "start index" loop version records every node of the tree:
def subsets(nums):
res, path = [], []
def dfs(start):
res.append(path[:]) # every node is a valid subset
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1) # only look forward → no reordering
path.pop()
dfs(0)
return res
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res; vector<int> path;
function<void(int)> dfs = [&](int start) {
res.push_back(path);
for (int i = start; i < (int)nums.size(); i++) {
path.push_back(nums[i]);
dfs(i + 1);
path.pop_back();
}
};
dfs(0);
return res;
}
Iterative alternative with bitmasks (n ≤ 20): mask m from 0 to 2ⁿ − 1, include nums[i] if bit i is set.
def subsets_bitmask(nums):
n = len(nums)
return [[nums[i] for i in range(n) if m >> i & 1] for m in range(1 << n)]
Handling duplicates
Sort first, then skip an element equal to its predecessor at the same tree level:
def subsets_with_dup(nums):
nums.sort()
res, path = [], []
def dfs(start):
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 level
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return res
Combinations and combination sums
| Variant | Recurse with | Duplicates in input |
|---|---|---|
| each element at most once | dfs(i + 1) | skip i > start and a[i] == a[i−1] |
| unlimited reuse | dfs(i) | input is usually distinct |
| fixed size k | stop when len(path) == k | — |
def combination_sum(candidates, target):
candidates.sort()
res, path = [], []
def dfs(start, remaining):
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
break # sorted → all later ones are too big
path.append(c)
dfs(i, remaining - c) # i, not i + 1: reuse allowed
path.pop()
dfs(0, target)
return res
Permutations
Order matters, so every unused element is a candidate at every level.
def permute(nums):
res, path = [], []
used = [False] * len(nums)
def dfs():
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])
dfs()
path.pop()
used[i] = False
dfs()
return res
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res; vector<int> path;
vector<bool> used(nums.size(), false);
function<void()> dfs = [&]() {
if (path.size() == nums.size()) { res.push_back(path); return; }
for (int i = 0; i < (int)nums.size(); i++) {
if (used[i]) continue;
used[i] = true; path.push_back(nums[i]);
dfs();
path.pop_back(); used[i] = false;
}
};
dfs();
return res;
}
With duplicates: sort, then skip nums[i] when i > 0 and nums[i] == nums[i−1] and not used[i−1] — this forces equal values to be used in their original order.
Constraint satisfaction: N-Queens
Place one queen per row. Track attacked columns and diagonals in sets for O(1) validity checks.
def solve_n_queens(n):
res = []
cols, diag, anti = set(), set(), set()
board = [["."] * n for _ in range(n)]
def dfs(r):
if r == n:
res.append(["".join(row) for row in board])
return
for c in range(n):
if c in cols or r - c in diag or r + c in anti:
continue
cols.add(c); diag.add(r - c); anti.add(r + c)
board[r][c] = "Q"
dfs(r + 1)
board[r][c] = "."
cols.remove(c); diag.remove(r - c); anti.remove(r + c)
dfs(0)
return res
Grid backtracking: word search
Mark the cell visited in place, recurse to neighbours, restore.
def exist(board, word):
R, C = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]:
return False
saved, board[r][c] = board[r][c], "#" # mark visited
found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
board[r][c] = saved # restore
return found
return any(dfs(r, c, 0) for r in range(R) for c in range(C))
For many words at once, walk a trie during the DFS (Word Search II).
Partitioning strings
At each position try every possible next piece; recurse on the remainder.
def partition(s):
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])
res, path = [], []
def dfs(start):
if start == n:
res.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
dfs(0)
return res
Pruning: the difference between TLE and AC
- Sort + break when the remaining candidates can only get worse (combination sum).
- Feasibility bounds: stop if the remaining elements can't fill the remaining slots (
n − i < k − len(path)). - Constraint sets for O(1) validity (N-Queens, Sudoku).
- Most-constrained-first: in Sudoku, fill the cell with the fewest legal digits first.
- Symmetry breaking: in k-partition, if placing an item into an empty bucket failed, don't try other empty buckets.
- Memoize if the same sub-state recurs → it's DP now.
Complexity
| Problem | Number of leaves | Time |
|---|---|---|
| Subsets | 2ⁿ | O(n · 2ⁿ) (copying each) |
| Permutations | n! | O(n · n!) |
| Combinations C(n, k) | C(n, k) | O(k · C(n, k)) |
| N-Queens | ≤ n! (pruned heavily) | ~O(n!) |
Space is O(n) for the recursion and path (plus the output).
Common mistakes
- Appending
pathinstead ofpath[:]/ a copy → every result ends up as the same (empty) list. - Forgetting to undo (
pop,used[i] = False, restoring the grid cell). i > 0instead ofi > startin duplicate skipping.- Recursing with
startinstead ofi + 1(or vice versa), producing permutations instead of combinations. - Not pruning — exponential algorithms need every cut you can find.
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.