When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Generate all valid combinations
- Constraint search
When another approach fits better
- Only one reachability answer is needed
- Subproblems overlap enough that memoized value computation - not output enumeration - is the goal
How it works#
Generate every unconstrained sequence, then validate only after it is complete.
Name the decision and candidate set at one depth.
Reject invalid partial choices before recursion.
Undo every mutation after the recursive call and copy a completed result.
InvariantAt depth d, the path contains exactly d committed choices satisfying every constraint checked so far.
Example and template#
Permutations
Tests state tracking when order matters.
Open the full problem brief- Choose 1
path [1]The path represents one valid partial assignment.
- Return
path []Undo restores the caller's exact state before the next sibling choice.
search(path, remaining):
if complete(path):
output copy(path)
return
for choice in candidates:
if invalid(choice, path): continue
choose(choice)
search(path, remaining after choice)
unchoose(choice)- Time
- Problem/output dependent; often O(b^d)
- Space
- O(d) excluding output
- Assumptions
- b is branching factor and d is maximum decision depth; pruning can reduce visited states but not the worst case automatically.
Pitfalls#
Common wrong approaches
Sibling branches inherit choices they never made.
All outputs can alias the same later-mutated list.
Edge cases
- Empty solution
- Duplicate candidates
- Reuse versus single use
- Constraint detected before completion
Interview narration
- “Each depth chooses one remaining candidate.”
- “The path is valid before I recurse, so invalid branches stop early.”
- “I undo the choice so the next branch starts from the same parent state.”
Practice#
Permutations
Tests state tracking when order matters.
Practice this problemList every valid assignment of shifts where no employee works adjacent slots.
Reveal the pattern decision
Backtracking fits because every output matters and adjacency can prune partial assignments.
Transfer problem
Generate unique combinations from duplicate values that meet a target.
Checkpoint: Sort candidates and skip equal siblings at the same recursion depth.
Follow-up variations
- Stop after the first valid output
- Count solutions with memoization instead of materializing them
Error-log prompts
- Was every mutation undone?
- Could I prune before descending?