This page is the "run every case" companion to the Backtracking topic note . There we learned the skeleton choose → explore → un-choose . Here we drive it through every edge case so you never meet a scenario you haven't already seen worked out.
Before any number appears, three plain words you must already own:
Definition The vocabulary this page uses
A partial solution is a half-finished answer — some choices made, some slots still empty. Picture a chessboard with 2 of 4 queens placed and rows 2–3 still blank.
A branch is one path down the choice-tree: "take element 0, then skip element 1, then…". Picture a road forking again and again; one branch = one route to a leaf.
To prune a branch is to cut it off before walking it, because we can prove nothing good lives down there. Picture snipping a dead twig off a tree so you never climb it.
These are just the DFS words from Depth-First-Search and Recursion-and-the-call-stack , renamed for the "build-and-undo" setting.
Every backtracking problem can throw one of these case classes at you. The examples below are labelled with the cell(s) they cover, so together they fill the whole grid.
Cell
Case class
What makes it tricky
Covered by
A Base/degenerate input (empty list, n=0, n=1)
Does the recursion still terminate and return something sensible?
Ex 1, Ex 6
B "In-or-out" branching (subsets)
Two children per node; copy-vs-reference trap
Ex 2
C "Pick-an-unused" branching (permutations)
The used[] reset; factorial blow-up
Ex 3
D Geometric pruning, all signs of a key (N-Queens diagonals: r−c can be negative, zero, positive )
Sign of r−c, sign of r+c, every quadrant of the board
Ex 4, Ex 5
E Impossible instance (no solution exists)
Must return empty / False, not crash or loop
Ex 5, Ex 6
F "Find ONE" vs "find ALL" (boolean short-circuit)
When to bubble True up the call stack
Ex 7
G Real-world word problem
Translate a story into choose/explore/undo
Ex 8
H Exam twist (subsets with duplicates )
Ordinary skeleton double-counts; needs a sort + skip
Ex 9
I Complexity limiting behaviour
How the node count grows as n →
Ex 10
The sign cases inside cell D are the ones people miss, so we spend two examples there — one per sign of the diagonal key.
Run subsets(nums) on nums = [] (the empty list). What comes back, and does the recursion even start?
Forecast: guess the output before reading on. How many subsets does the empty set have?
Steps.
Call bt(0). Since len(nums) == 0, the very first check if i == len(nums) is if 0 == 0 → true .
Why this step? The base case is the only thing that can fire when there is nothing to branch on — it must handle "no elements" or the function would try to read nums[0] and crash.
We append path[:], and path is still []. So res = [[]].
Why this step? The empty set is itself a valid subset — the unique subset of nothing. Recording it is correct, not a bug.
Return. No branching ever happens.
Verify: number of subsets should be 2 n = 2 0 = 1 []. ✓ The result is a list containing one empty list, not an empty list — a subtle but real distinction.
For nums = [7], trace subsets and show why writing res.append(path) (no [:]) breaks it.
Forecast: with the buggy line, what would the two stored subsets look like after the whole call finishes ?
Steps.
bt(0): not the base case. First child: bt(1) with path still [] → records [].
Why this step? The "skip" branch always runs first here, giving the without-7 subset.Back in bt(0): path.append(7) → path = [7]. Call bt(1) → records [7]. Then path.pop() → path = [].
Why this step? This is the choose → explore → un-choose on element 7. The pop() restores state so no sibling inherits the 7.
Correct result: [[], [7]].Buggy version (res.append(path)): both records point at the same list object. After step 2's pop(), that shared list is [], so both entries read as [] → result prints [[], []].
Why this step? A Python list name is a reference ; storing it stores the address, not a snapshot. path[:] makes a fresh snapshot.
Verify: correct output length = 2 1 = 2 [] and [7]) ✓. The buggy output has the right length but wrong contents — proof that "it ran without error" is not proof of correctness.
List every permutation of nums = [1,2,3] and count them. Then explain what breaks if you forget used[i] = False.
Forecast: how many orderings? And if the reset is missing, how many will you get?
Steps.
First slot has 3 choices, second has 2 (one used up), third has 1: 3 × 2 × 1 = 3 ! = 6 Why this step? Each level consumes one element, so the choice-count shrinks by one per level — that is exactly the factorial pattern.
Depth-first walk gives: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].
Why this step? We fix the first element (1, then 2, then 3) and recurse; within each, we fix the second, etc. DFS visits them in this lexicographic order.
If used[i] = False is dropped: after finishing all permutations starting with 1, elements stay marked used, so the "start with 2" branch finds nothing free and produces zero further permutations — you'd get only the ones down the very first path, often just [1,2,3].
Why this step? used[] is shared mutable state (same trap family as Ex 2). The un-choose must clear it so sibling branches start clean.
Verify: count = 6 = 3 ! 2 6/3 = 2
On a board, a queen sits at (r,c) = (2,0). Using the r−c (↘) and r+c (↗) keys, list every square this queen attacks diagonally , and note the sign of each key.
Forecast: its r−c key — is it negative, zero, or positive? Guess before computing.
What to see in the figure above: the amber ★ is our queen at (2,0). The solid cyan line threads every cell on the ↘ diagonal r−c = 2 (the cyan dots at (3,1),(4,2),(5,3)); the dashed white line threads the ↗ anti-diagonal r+c = 2 ((1,1),(0,2)). The amber ring marks (1,1), whose key r−c = 0 — the reader should notice the cyan line's label reads a positive constant while the ringed cell shows the zero case, so both signs live on one picture.
Steps.
↘ key: r − c = 2 − 0 = 2 positive . Every cell with r−c = 2 shares this diagonal: (2,0),(3,1),(4,2),(5,3),….
Why this step? Moving one step down-right adds 1 to both r and c, so r−c is unchanged — that constant is the diagonal's fingerprint (see the parent note's derivation).
↗ key: r + c = 2 + 0 = 2 r+c = 2: (2,0),(1,1),(0,2).
Why this step? Moving one step up-right subtracts 1 from r (row goes up) and adds 1 to c (column goes right), so the two changes cancel and r+c is unchanged — that constant labels the anti-diagonal. Walking the same ↗ line downward-left does the reverse and is equally invariant.
The cell (1,1) has r−c = 0 — the zero case, the true main diagonal. Any queen there would clash with a queen having key 0.
Why this step? Zero is a legitimate diagonal key, not a special-case bug. The set diag stores it like any other integer.
Verify: for (3,1): r − c = 3 − 1 = 2 (0,2): r + c = 0 + 2 = 2
(a) Find one valid 4-Queens placement and confirm each queen's r−c (including a negative key) is unique. (b) Show 3-Queens returns an empty list.
Forecast: for n=3, how many solutions? Zero, one, or two?
What to see in the figure above: four amber ★ queens, one per row, at (0,1),(1,3),(2,0),(3,2). Below each queen is its cyan r−c label. The reader should scan those four labels — -1, -2, 2, 1 — and confirm no two match (that is the diagonal-safety proof done by eye), and note that two of them are negative : negative keys are stored raw, exactly like the positive ones in the previous figure.
Steps (part a).
A known 4-Queens solution: row 0→col 1, row 1→col 3, row 2→col 0, row 3→col 2. Positions (0,1),(1,3),(2,0),(3,2).
Why this step? We place one queen per row (the smart state from the parent note), so rows are automatically conflict-free.
Column keys: {1,3,0,2} — all four distinct ✓, so no column clash.
Why this step? cols set membership is the O ( 1 )
↘ keys r−c: 0 − 1 = − 1 1 − 3 = − 2 2 − 0 = 2 3 − 2 = 1 {-1,-2,2,1}. Note the negative values −1,−2: negative diagonal keys are perfectly normal and must be stored as-is.
Why this step? Sets handle negative integers fine — no abs() or offset needed, contrary to a common beginner fix.
↗ keys r+c: 1 , 4 , 2 , 5 {1,4,2,5}, all distinct ✓.
Steps (part b).
5. For n=3, try row 0. Placing at col 0 forces row 1 to avoid col 0 (column), col 1 (↘, key 0 clash with 1-1)… every row-2 square ends up attacked. All three first-row choices die. res stays [].
Why this step? Backtracking explores all branches when collecting all solutions; when every branch prunes to nothing, the honest answer is the empty list — not an error.
Verify: (a) all three key-sets have 4 distinct entries ✓. (b) count of 3-Queens solutions = 0 = 2
What does solveNQueens(n) return for n=0 and n=1? Be precise about the serialization of a board.
Forecast: an empty board — is that a solution or a non-solution?
Steps.
Recall the output format from the parent note: each board is serialized as a list of strings , one string per row, where each character is 'Q' or '.'. The full return value is a list of such boards (a list of lists of strings). So ["Q"] means "one board, whose single row is the one-character string Q", and [] means "one board with zero rows ".
Why this step? Without pinning the format, [] is ambiguous — the confusion is "empty result" vs "empty board". Here [] is a board (no rows), and it sits inside the outer result list.
n=1: bt(0) places the single queen at col 0 (no keys exist yet to clash with), then bt(1) hits r == n → records one board ["Q"]. Result: [["Q"]].
Why this step? One queen alone can attack nobody, so a 1 × 1 n=0: bt(0) sees r == 0 == n immediately → records the empty board [] (zero rows) and stops. Result: [[]].
Why this step? Zero queens on a zero-size board vacuously satisfies "no two attack" — the base case fires before any loop. The outer list [[]] holds one board that happens to have no rows.
Verify: solution counts (length of the outer list): n=0 → 1, n=1 → 1 ✓. (For contrast, n=2 and n=3 both give 0; n=4 gives 2.) The degenerate cases return one board each, not zero — the inner board for n=0 is [], a list of zero row-strings.
A Sudoku solver returns True up the stack the instant it fills the grid. Contrast the number of leaves visited with an "enumerate all solutions" version, on a tiny puzzle that has exactly one solution.
Forecast: if the answer lives down the first branch tried, how many other branches does the "find-one" version explore?
Steps.
"Find-one" version: if bt(): return True propagates success without trying remaining digits. If the correct digit is found first at every cell, it walks a single root-to-leaf path.
Why this step? The boolean lets a deep success cancel all pending loop iterations above it — that's the whole point of returning True.
"Find-all" version would keep looping every remaining digit at every cell even after finding the solution, exploring the full tree.
Why this step? Collecting all answers means you may never short-circuit; you pay for every branch.
Concrete count: suppose a puzzle needs k = 3 k + 1 = 4 9 Why this step? This is the practical reason CSP solvers separate "satisfiability" (one) from "enumeration" (all).
Verify: find-one path length = k + 1 = 4 k = 3
You have coins [1, 5, 6, 8]. Using backtracking's in/out branching, list every subset that sums to exactly 11.
Forecast: more than one way? Guess how many before enumerating.
Steps.
This is Pattern 1 (subsets) with a target test: at each coin, branch skip vs take , and at a leaf check sum(path) == 11.
Why this step? "Choose a set of coins" is literally the in-or-out decision — the subset skeleton fits with zero changes.
Enumerate the sums that hit 11: {5,6} → 5 + 6 = 11 {1,?}… 1 + 8 = 9 1 + 5 + 6 = 12 {8,?} … 8 + 1 = 9 Why this step? We only keep leaves passing the constraint; every other branch is discarded at the leaf.
Optional pruning: if a running sum already exceeds 11 and all coins are positive, cut the branch early (that's Branch-and-Bound flavour).
Why this step? Positive weights let us prune before the leaf — turning brute force into true backtracking.
Verify: the qualifying subsets are exactly [[5,6]]; count = 1 5 + 6 = 11 [1,5,6,8] sums to 11 ✓.
nums = [1, 2, 2]. The plain subset skeleton produces duplicate subsets. List the unique subsets and write the sort-and-skip fix in code.
Forecast: how many subsets does plain code emit (2 3
Steps.
Plain skeleton emits 2 3 = 8 [2]).
Why this step? The template treats positions as distinct; equal values collapse, creating duplicates.
Sort nums → [1,2,2] so equal values sit adjacent, then use an index-loop builder that skips a duplicate when it is not the first copy chosen at the current level:
def subsetsWithDup (nums): res, path = [], [] nums.sort() # equal values become adjacent def bt (start): res.append(path[:]) # every node is a valid subset for i in range (start, len (nums)): if i > start and nums[i] == nums[i - 1 ]: continue # skip duplicate sibling branch path.append(nums[i]) # choose bt(i + 1 ) # explore (i+1: no reuse) path.pop() # un-choose bt( 0 ) return res Why this step? Sorting is what makes duplicates adjacent, so the single test nums[i] == nums[i-1] can spot them. The guard i > start permits the first copy at a level (so [2,2] still forms by taking twins consecutively via bt(i+1)) while blocking the second copy from starting a duplicate sibling branch. This kills repeats at the source by pruning — cheaper than generating all 8 and de-duplicating afterward.Unique subsets of [1,2,2]: [], [1], [2], [1,2], [2,2], [1,2,2].
Why this step? Each distinct multiset now appears exactly once because the skip rule enforces one canonical build order (duplicates are always taken left-to-right, never re-started as a sibling).
Verify: unique count = 6 2 × 3 = 6 1 is present/absent ×2, the pair contributes 0, 1, or 2 copies ×3) ✓.
Roughly how many tree nodes does the subset backtracker visit for general n n Time-Complexity-of-Recursive-Algorithms .
Forecast: which explodes faster — 2 n n !
What to see in the figure above: the vertical axis is a log scale , so straight-ish lines are actually exponential/factorial growth. The cyan curve is the subset leaf count 2 n amber curve is the permutation leaf count n ! below cyan (at n=3, 6 < 8 n=3 and n=4. After the crossing, amber pulls away far faster: that visual gap is why permutation problems become intractable sooner.
Steps.
Subsets: the recursion tree is a full binary tree of height n 2 n + 1 − 1 Why this step? A perfect binary tree of height n 2 n + 1 − 1 1 + 2 + 4 + ⋯ + 2 n bt calls the subset skeleton makes.
Permutations: leaves alone number n ! n ! 2 n n 4 ! = 24 > 2 4 = 16 Why this step? Factorial multiplies by an ever-larger factor each level, while the exponential multiplies by a fixed 2 — so factorial must eventually win, and we can pin down exactly where the crossover happens (see figure).
Pruning changes the effective base but not this asymptotic story — that's why N-Queens (n ! n Why this step? Backtracking shrinks the constant and the branching factor, but exponential/factorial growth remains the ceiling — so Dynamic-Programming or Branch-and-Bound is reached for when even pruned backtracking is too slow.
Verify: subset nodes at n = 3 2 4 − 1 = 15 3 ! = 6 < 2 3 = 8 4 ! = 24 > 2 4 = 16 n = 3 n = 4
Recall Which cell does each example fill?Ex1 base/empty (A) ::: subsets([]) → [[]], one subset
Ex2 in/out + copy trap (B) ::: [[],[7]]; buggy version stores two []
Ex3 pick-unused + reset (C) ::: 6 permutations of [1,2,3]
Ex4 diagonal keys, zero & positive (D) ::: queen at (2,0), keys r−c=2, r+c=2
Ex5 negative key + impossible (D,E) ::: 4-Queens solvable, 3-Queens empty
Ex6 degenerate boards (A,E) ::: n=0 → [[]], n=1 → [["Q"]], each one solution
Ex7 one-vs-all short-circuit (F) ::: boolean True cancels sibling branches
Ex8 word problem (G) ::: only [5,6] sums to 11
Ex9 duplicates twist (H) ::: 6 unique subsets of [1,2,2]
Ex10 growth (I) ::: 2^{n+1}-1 nodes; n! beats 2^n past n=3
Mnemonic Run the matrix, not the moodBefore you submit backtracking code, mentally push it through A→I : empty input, both branch shapes, every sign of the key, the impossible instance, one-vs-all, and the growth. If any cell surprises you, you found your bug.