Backtracking
Intermediate · 24 min read · Problem-Solving Patterns, Backtracking
Subsets, combinations, permutations and constraint puzzles with one template.
"Generate all subsets." "All permutations." "Every way to place 8 queens." These problems ask for every valid arrangement, and that sounds like it needs a different clever trick each time. It doesn't.
The decision tree
For subsets of [1, 2, 3], each level decides which element to add next, only looking forward (so [2, 1] is never produced after [1, 2]):
The template
Three decisions customise it for each problem:
Subsets and combinations: move forward with start
The start index is what makes these combinations (order doesn't matter): you never look back, so each set is produced once.
Handling duplicates in the input
With input [1, 2, 2], naive subsets produce [1, 2] twice (using either 2). The fix is always the same: sort, then at a given depth skip a value equal to the previous one — choosing the second 2 at the same position would build exactly the same subtree as the first.
Permutations: track what's used
Order matters now, so every unused element is a choice at every step — there's no start. A boolean[] used marks what's already in the path.
Building strings
Instead of generating all strings and filtering, only make choices that can still lead to a valid answer: add ( while you have some left, add ) only if it would close an open one.
Constraint puzzles
The "path" is the set of grid cells used so far. Mark a cell while it's on the path, and restore it when backtracking so other paths can use it:
How expensive is backtracking?
You can't beat "the size of the output" when you must list everything — so say that out loud. Pruning shrinks the tree you explore, not the answers you must produce.
Practice ladder
Interview questions
- Why must you copy the path when adding it to the results?
- How do you avoid duplicate results when the input contains duplicates?
Further reading
Key takeaways
- Backtracking = DFS over a decision tree: choose, explore, un-choose.
- Combinations/subsets: a start index (never look back); permutations: a used[] array.
- Reuse allowed → recurse with i; once each → i + 1.
- Duplicates: sort, then skip equal values at the same depth (i > start).
- Prune early; copy the path when storing it; restore grid cells.
- If only a count or the best value is needed, consider DP instead.