Recognition cue. The problem says all, every, generate, enumerate, or asks for combinations, permutations, subsets, partitions, or arrangements. The constraint is small — n up to about 20 for subsets, up to about 10 for permutations — which is the setter telling you an exponential answer is expected.
The move. Build a partial answer one choice at a time. When it is complete, record it. When it cannot possibly work, abandon it. Undo each choice on the way back out.
Every backtracking solution has exactly these, in this order. Write them as four separate thoughts.
python
def backtrack(state): if is_complete(state): # 1. BASE CASE record(state) return for choice in choices(state): # 2. THE CHOICES if not allowed(choice): # 3. THE CONSTRAINT — this is the pruning continue make(choice) # 4a. do it backtrack(state) # recurse undo(choice) # 4b. UNDO — the "backtracking"
The skeleton, line by line.state is the partial answer built so far. is_complete asks whether it is a finished answer, such as a full-length permutation. record saves a copy of it. choices lists the possible next steps from here. allowed rejects a step that breaks a rule, before any work is spent below it. make applies the step to the shared state, the recursive call explores everything that follows from it, and undo takes the step back, so the next choice in the loop starts from exactly the state this call was given.
Part 3 is where all the performance is. Checking validity as you choose prunes an entire subtree. Checking it only on complete answers is brute force wearing a recursion costume, and it is the difference between 8^8 and about 2,000 in N-Queens.
Part 4b is where all the correctness is. Whatever you add before recursing must be removed after. Forget it and state leaks between branches, and the results are quietly wrong.
At index i, either take nums[i] or do not. Then move to i + 1.
python
def backtrack(i, path): if i == len(nums): result.append(path[:]) # copy! return path.append(nums[i]) # take it backtrack(i + 1, path) path.pop() # undo backtrack(i + 1, path) # skip it
Two branches per node, n levels deep → 2^n leaves. Use when each element is independently in or out.
Shape 2 — choose the next element, moving forward (combinations)
A loop from a start index, and the recursive call moves the start forward. Order does not matter, so [1,2] and [2,1] are the same answer and only one is generated.
python
def backtrack(start, path): result.append(path[:]) # every node is an answer, for subsets for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) # i + 1: never look back path.pop()
i + 1 versus i is the whole difference between two problem families.i + 1 means each element is used at most once. Passing i means it can be reused — that is Combination Sum.
Shape 3 — choose any unused element (permutations)
A loop over everything, with a used-marker. Order matters, so [1,2] and [2,1] are both answers.
python
def backtrack(path, used): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) backtrack(path, used) path.pop() used[i] = False
When the input contains repeated values, you will generate the same answer twice. Sort first, then skip a value that equals its predecessor at the same level of the tree:
python
nums.sort()for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # a sibling already tried this value
i > start, not i > 0. The guard must skip duplicates among siblings — different choices at the same position — not duplicates along the path. Using i > 0 would wrongly forbid [2, 2] when there really are two 2s available.
Say that condition out loud when you write it. It is the single most-missed detail in this chapter.
result.append(path[:]) # a copy — NOT result.append(path)
path is one shared list that keeps changing. Appending it without copying stores a reference, and by the end every entry in result is the same empty list. In JavaScript, [...path].
This bug produces output that looks the right shape but is entirely wrong, so check for it every time.
You cannot beat the size of the output. If a problem asks for all 2^n subsets, the answer alone is exponential.
So the complexity is roughly (number of results) × (cost of building each one):
subsets — O(2^n \times n)
permutations — O(n! \times n)
combination sum — bounded by the tree size, hard to state exactly, and saying so honestly is better than inventing a formula
Pruning does not change the asymptotic bound — it changes the constant, and the constant is everything. N-Queens without pruning tries 8^8 \approx 16.7 million placements; with column and diagonal checks at the moment of placing, it explores about 2,000.
"Walk me through your recursion tree for n = 3." Draw it. If you cannot draw it, the code will not be right.
"Where does the pruning happen?" Point at the constraint check and say what subtree it removes.
"What is the complexity?" The output size times the cost per result, and then say that pruning changes the constant rather than the exponent.
"Why i + 1 here and i there?" Reuse allowed or not.
"How do you avoid duplicate answers?" Sort, then skip equal siblings with i > start.
"Could you do it iteratively?" For subsets, yes — start with [[]] and for each element append copies of everything so far with that element added. For the rest, an explicit stack of states, which is messier than the recursion.
One thing to volunteer: name the four parts as you write them — choices, constraint, recurse, undo — and say which of the three shapes you picked and why. That framing is what makes the next backtracking problem easy instead of a fresh puzzle.
Recall
Backtracking is DFS over a tree you never build. Each node is a partial answer; each edge is one choice.
Four parts: base case · the choices · the constraint (this is the pruning) · make, recurse, undo.
Three shapes: include/exclude · loop from a start index (order does not matter) · loop over all with a used-marker (order matters).
i + 1 = each element used once. i = reuse allowed. One character apart, two problem families.
Duplicates: sort first, then if i > start and nums[i] == nums[i-1]: continue. It is i > start, not i > 0.
Copy the path when recording: path[:] or [...path]. Otherwise every result is the same reference.
Complexity is output size × cost per result. Pruning changes the constant, not the exponent — and the constant is everything.
Next:4.18.1 Subsets — the simplest tree in the chapter, and the one to draw before writing anything.