Recursion & Backtracking
Explore every choice, undo it, and try the next. The template behind subsets, permutations, combinations, N-Queens, Sudoku and word search.
Recursion in one sentence
A recursive function solves a problem by calling itself on a smaller version, with a base case that stops. Draw the recursion tree: the number of nodes × the work per node is the complexity.
Backtracking
Backtracking is DFS over the tree of decisions. At each node you choose an option, explore further, then un-choose it (restore the state) before trying the next option. If a partial choice can already be ruled out, prune that whole branch, which is what makes N-Queens and Sudoku fast enough.
The universal template
def backtrack(state):
if state is a complete solution:
record a COPY of it
return
for choice in options(state):
if not valid(choice): continue # prune
make(choice)
backtrack(state)
undo(choice)
Variations
| Problem | Loop over | Key detail |
|---|---|---|
| Subsets | i from start |
record at every node |
| Combinations / combination sum | i from start |
recurse with i (reuse) or i + 1 (no reuse) |
| Permutations | all i not used |
used[] array |
| With duplicates (Subsets II) | sorted input | skip nums[i] == nums[i−1] at the same level |
| Grid search (word search) | 4 directions | mark the cell, recurse, restore it |
| N-Queens | columns of the current row | sets for columns and both diagonals |
Code template
def subsets(nums):
res, path = [], []
def backtrack(start):
res.append(path[:]) # record a copy
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1) # explore
path.pop() # un-choose
backtrack(0)
return res
def permutations(nums):
res, path, used = [], [], [False] * len(nums)
def backtrack():
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])
backtrack()
path.pop(); used[i] = False
backtrack()
return resList<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), res);
return res;
}
void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // record a copy
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // choose
backtrack(nums, i + 1, path, res); // explore
path.remove(path.size() - 1); // un-choose
}
}void backtrack(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
res.push_back(path); // record a copy
for (int i = start; i < (int)nums.size(); i++) {
path.push_back(nums[i]); // choose
backtrack(nums, i + 1, path, res); // explore
path.pop_back(); // un-choose
}
}
vector<vector<int>> subsets(const vector<int>& nums) {
vector<vector<int>> res; vector<int> path;
backtrack(nums, 0, path, res);
return res;
}function subsets(nums) {
const res = [], path = [];
const backtrack = start => {
res.push([...path]); // record a copy
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose
backtrack(i + 1); // explore
path.pop(); // un-choose
}
};
backtrack(0);
return res;
}Complexity
Exponential by nature: subsets O(n·2ⁿ), permutations O(n·n!). Space is O(depth) plus the output. Pruning does not change the worst case but makes real inputs fast.
Practise this pattern (6 problems)
Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.
| # | Problem | Difficulty | |
|---|---|---|---|
| 64 | Subsets | Medium | |
| 65 | Permutations | Medium | |
| 66 | Combination Sum | Medium | |
| 67 | Word Search | Medium | |
| 68 | Generate Parentheses | Medium | |
| 69 | N-Queens | Hard |
Common mistakes
- Appending
pathitself instead of a copy (all results end up identical and empty). - Forgetting to undo the choice, so state leaks into sibling branches.
- Generating duplicates: sort, then skip equal neighbours at the same depth.