When to use. You must enumerate combinations under constraints; no cheap DP recurrence is obvious.
Complexity. Time O(branching^depth) — always state it; prune hard. Space O(depth) for the path plus output size.
Who gets asked. Subset/permutation generation is intern/mid. Pruning and constraint boards are mid/senior.
Prereq. Recursion; arrays.
Backtracking
Choose, recurse, undo. You enumerate a tree of partial answers. Interviews want pruning and a clear complexity, not a magic recursive one-liner.
The idea
State is the path so far plus what is still available (index, used mask, remaining budget). On a leaf, copy the path into the answer list.
Subsets: at each index, skip or take. Permutations: swap / used-array. Constraint boards: try a value, recurse, revert the cell.
If overlapping subproblems have an optimal value (not a list of all paths), you probably want DP instead. Backtracking is for enumeration and constraint search.
Worked example
All subsets
Distinct numbers. Return every subset, including empty and full. Example: [1, 2] → [], [1], [2], [1,2]. Order of subsets does not matter.
Start at index 0 with an empty path.
Branch: skip nums[i], or push it and continue, then pop.
When i === n, snapshot the path. 2^n leaves — say that out loud.
function subsets(nums) {
const out = [];
const path = [];
function dfs(i) {
if (i === nums.length) {
out.push(path.slice());
return;
}
dfs(i + 1);
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
dfs(0);
return out;
}
Time O(n · 2^n) to copy each subset. Space O(n) recursion plus output.
Practice shapes
Original prompts — same family as interview questions, not copied statements.
Permutations of distinct items
All orderings of a list of unique values. n! results — mention that before coding.
Aim: O(n · n!) time
Combination budget
Numbers (reusable) and a target. All combinations that add to the target. Skip a branch when the remaining budget is negative.
Aim: Exponential; prune on remainder
Place n tokens
n×n board. Place n tokens so no two share a row, column, or diagonal. Count or list placements. Classic prune-on-attack.