Part 1 · Concepts · Recursion and backtracking
Backtracking
Build answers one choice at a time, explore each choice, and undo it before trying the next.
How it works
Template: choose, explore (recurse), un-choose. Subsets: each item is taken or skipped, giving 2^n results. Permutations: at each position try every unused item, giving n! results. Pruning (stopping early when a path can't work) is what makes it practical.
| subsets | O(n · 2^n) |
| permutations | O(n · n!) |
Reach for it when
- Generate all combinations, subsets, permutations
- Puzzles: N-queens, sudoku, word search
- Small n (usually under about 20)
Implementation (JavaScript, tested)
function subsets(nums) {
const out = [],
path = [];
const go = i => {
if (i === nums.length) {
out.push([...path]);
return;
}
go(i + 1); // skip nums[i]
path.push(nums[i]);
go(i + 1);
path.pop(); // take nums[i], then undo
};
go(0);
return out;
}
function permutations(nums) {
const out = [],
path = [],
used = new Array(nums.length).fill(false);
const go = () => {
if (path.length === nums.length) {
out.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]); // choose
go(); // explore
path.pop();
used[i] = false; // un-choose
}
};
go();
return out;
}Traps
- Pushing path itself instead of a copy: every result ends up the same array.
- Forgetting to undo (pop) after exploring.
In real systems: Generating test matrices or config combinations, constraint solvers, regex engines backtrack on failed matches.
Say out loud: It's exponential by nature, so I'll prune as early as possible. Choose, explore, undo.