Trees & Recursion
Backtracking
🌀
Picture this
In the hedge maze you try a path, hit a dead end, and carefully retrace every step — undoing footprints as you go.
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
all combinationspermutationssubsetsgeneraten-queensvalid arrangements
Ask yourself
- Enumerate ALL valid configurations?
- Permutations / combinations / subsets / placements?
- Choose → recurse → un-choose.
Canonical template
function backtrack(path: Choice[], choices: Choice[]): void {
if (done(path)) {
res.push([...path]);
return;
}
for (const choice of choices) {
path.push(choice);
backtrack(path, nextChoices(choice));
path.pop();
}
}
Common pitfalls
Forgetting to undo the choice after recursion.
Appending a reference instead of a copy of
path.