What you will learn
- Understand the call stack and how recursion builds solutions layer by layer
- Apply the backtracking template: choose, explore, unchoose
- Generate permutations, combinations, and subsets using a single pattern
- Recognize when pruning can drastically reduce the search space
Why this matters
Backtracking powers solutions to combinatorial problems that appear constantly in interviews: permutations, subsets, N-Queens, word search, Sudoku. Once you internalize the template, these problems become mechanical rather than mysterious.
The backtracking template
Every backtracking problem follows the same skeleton:
def backtrack(candidates, path, result):
if is_goal(path):
result.append(path[:]) # copy the current path
return
for choice in candidates:
if not is_valid(choice, path):
continue # prune
path.append(choice) # choose
backtrack(next_candidates, path, result) # explore
path.pop() # unchoose (backtrack)Subsets (power set)
Generate all subsets of [1, 2, 3].
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # every path is a valid subset
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # move forward, no repeats
path.pop()
backtrack(0, [])
return result
# subsets([1,2,3]) -> [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Time: O(n * 2^n) — 2^n subsets, each up to size n to copy.
Permutations
def permutations(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return resultTime: O(n * n!) — n! permutations, each of length n.
Combination Sum
Find all combinations of candidates that sum to target (elements can be reused).
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # prune: sort first, skip too-large
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, not i+1: reuse allowed
path.pop()
candidates.sort()
backtrack(0, [], target)
return resultThe power of pruning
Without pruning, backtracking explores every branch. Adding early termination (like if candidates[i] > remaining: break) can cut the search space by orders of magnitude. Always sort the candidates if it enables pruning.
Recursion vs. iteration
Any recursion can be converted to iteration with an explicit stack, but backtracking is almost always cleaner as recursion. The call stack naturally tracks your "path" of choices.
Quick quiz
Q: In the backtracking template, what does the "unchoose" step (path.pop()) accomplish?
How to explain it in an interview
"I'd use the backtracking template: maintain a current path, iterate over choices, and for each valid choice, add it to the path, recurse, then remove it to backtrack. For subsets I'd add the current path at every node; for permutations I'd add it only at leaf nodes. I always sort the candidates first so I can prune branches early when the remaining target becomes negative."