IntermediateBacktracking
Backtracking: choose, explore, un-choose
Make a choice, recurse, then undo it before trying the next. That one template generates subsets, permutations and combinations.
The idea
Backtracking builds answers one decision at a time. At each step: add a choice to the current path, recurse to make the remaining choices, then remove it so the path is clean for the next option.
For subsets, each element is either in or out, which gives 2ⁿ results.
Worked example
Subsets of [1, 2]
- start [] → record []
- choose 1 → [1] → record → choose 2 → [1,2] → record → undo 2 → undo 1
- choose 2 → [2] → record → undo → result [], [1], [1,2], [2]
In code (Python)
def subsets(nums):
result, path = [], []
def explore(start):
result.append(path[:]) # copy the current choice
for i in range(start, len(nums)):
path.append(nums[i]) # choose
explore(i + 1) # explore
path.pop() # un-choose
explore(0)
return resultO(n · 2ⁿ) for subsets: that many results to write out.
How to spot it
- “all subsets / permutations / combinations”, puzzles like N-Queens and word search.
Common mistakes
- Appending `path` instead of a copy, so every result ends up the same list.
- Forgetting to undo the choice.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →