Worked examples — Backtracking — state-space tree, pruning

This page is the exhaustive drill room for Backtracking — state-space tree, pruning. The parent note gave you the rhythm (CHOOSE → EXPLORE → UN-CHOOSE) and the idea of pruning. Here we hit every kind of case a backtracking problem can throw at you, so no scenario surprises you in an exam or interview.

---

The scenario matrix

Every backtracking problem lives in one (or more) of these cells. The last column names the worked example that covers it.

Cell	Case class	What makes it tricky	Covered by
A	Solution exists, found after backtracks	you hit dead-ends before success	Ex 1 (N-Queens n=4)
B	No solution exists	tree fully explored, nothing recorded	Ex 2 (N-Queens n=3)
C	Degenerate: empty input	base case fires immediately	Ex 3 (subsets of [])
D	Degenerate: target impossible	prune kills everything	Ex 4 (subset-sum target 100)
E	Count ALL solutions	don't stop at first; keep the counter	Ex 5 (all subsets sum=6)
F	Pruning does nothing (worst case)	adversarial input, full $b^d$	Ex 6 (permutations, no constraint)
G	Pruning does everything (bound at root)	one check kills the whole tree	Ex 7 (subset-sum, all too big)
H	Real-world word problem	translate words → candidates + isValid	Ex 8 (assign tasks)
I	Exam twist: "count nodes visited"	reason about the tree, not the answer	Ex 9 (node-count analysis)
J	Find ONE solution, stop immediately	return up the whole recursion on first hit	Ex 10 (first subset sum=6)

We link the deep-dive prerequisites where they help: Recursion, Depth-First-Search, N-Queens, Permutations-and-Combinations, Time-Complexity, Branch-and-Bound.

---

Ex 1 — Cell A: N-Queens n=4, solution after backtracks

Let us define the attack test precisely, because everything depends on it.

The figure below plants a single queen at row 0, column 1 and paints every square it attacks: orange squares share its column, red squares satisfy $|r-i|=|c-\text{col}[i]|$ and so lie on a diagonal. Trace one red square with your finger — say row 2, column 3 — and confirm $|2-0|=2=|3-1|$. That is exactly the equality our test checks; the picture is the test made visible.

Steps (columns numbered 0..3):

1. Row 0 → col 0. State [0]. Why this step? We always try columns left-to-right; col 0 has no earlier rows to conflict with, so it's trivially valid.

2. Row 1: col 0 ✗ (same column as row 0). col 1 ✗ (diagonal: $|1-0|=|1-0|$). col 2 ✓ → [0,2]. Why this step? We pruned cols 0 and 1 before recursing — their entire subtrees (all of rows 2 and 3 beneath them) are never built.

3. Row 2: we test each column against the two earlier queens at row 0 col 0 and row 1 col 2.

   • col 0 ✗ — same column as row 0.
   • col 1 ✗ — diagonal from row 1 col 2: $|2-1|=|1-2|=1$.
   • col 2 ✗ — same column as row 1.
   • col 3 ✗ — diagonal from row 1 col 2: $|2-1|=|3-2|=1$ (against row 0 col 0 it is fine, since $|2-0|=2$ but $|3-0|=3$).

   No column survives → dead end → backtrack. Why this step? No column survives all constraints, so this node is a dead-end leaf. We undo row-1's choice and try its next sibling.

4. Back at Row 1, try col 3 → [0,3]. Row 2: col 1 ✓ → [0,3,1]. Row 3: no valid col → dead end → backtrack again. Why this step? Demonstrates backtracking going up two levels when a whole sub-branch fails.

5. Eventually the search reaches [1,3,0,2] and [2,0,3,1] — the two full solutions.

The next figure shows both finished boards side by side. Notice in each that no two blue queens share a row (one per row by construction), a column (the vertical-alignment check), or a diagonal (the $|r-i|=|c-\text{col}[i]|$ check) — that is what "no two attacking" looks like when the search succeeds.

Verify: the two boards are [1,3,0,2] and [2,0,3,1]. Sanity-check [1,3,0,2] by hand: columns {1,3,0,2} are all distinct ✓; the diagonal test on rows $(0,1)$ gives $|0-1|=1$ but $|1-3|=2$, so they differ ✓. Repeating this for all six row-pairs shows no conflict. Answer: 2 solutions.

---

Ex 2 — Cell B: N-Queens n=3, NO solution

Steps:

1. Row 0 → col 0 → [0].
2. Row 1: col 0 ✗(col), col 1 ✗(diag), col 2 ✓ → [0,2]. Why this step? Only col 2 survives — pruning already narrowed us to one path.
3. Row 2: col 0 ✗(col=row0), col 1 ✗(diag from row1 col2: $|2-1|=|1-2|$), col 2 ✗(col=row1). Dead end. Backtrack to row 1 — no more columns. Backtrack to row 0.
4. Row 0 → col 1 → [1]. Row 1: col 0 ✗(diag), col 1 ✗(col), col 2 ✗(diag). Dead end immediately. Why this step? Center-start poisons both neighbours by diagonal — pruning kills row 1 entirely.
5. Row 0 → col 2 → mirror of col-0 case, also fails.
6. All three starting columns exhausted → record nothing → 0 solutions.

Verify: The search records zero solutions. This is the "empty result" case — the algorithm terminates correctly having proved no arrangement works. Answer: 0 solutions. (Machine-checked: no valid [c0,c1,c2] permutation exists.)

---

Ex 3 — Cell C: subsets of the EMPTY list

Steps:

1. For the empty list, len(list) = 0, so at the root i = 0 = len(list) and is_complete is true immediately — there are no decisions to make. Why this step? The base case of any recursion (see Recursion) is the degenerate input; here it fires before any branching.
2. record(state) fires once on the empty partial solution.

Verify: number of subsets of a set of size $n$ is $2^n$; for $n=0$, $2^0=1$ — the empty subset $\{\}$ itself. Answer: 1 subset (the empty set). A common bug is to return 0 subsets; the correct count is 1.

---

Ex 4 — Cell D: subset-sum with impossible target

Steps:

1. At the root, running_sum = 0, remaining_total = 2+4+6+8 = 20, target = 100.
2. Bound test: $0+20=20<100$ → prune at the root. The entire tree is cut before a single element is examined. Why this step? One arithmetic comparison replaces exploring all $2^4=16$ leaves.

Verify: max reachable sum $=20<100$, so 0 subsets sum to 100, and the search visits essentially 1 node. Answer: 0 subsets.

---

Ex 5 — Cell E: count ALL subsets that sum to 6

Steps:

1. Include 2 (sum 2). Include 4 (sum 6) ✓ → record {2,4}. Now try excluding/including 6, 8 — any inclusion pushes sum past 6, pruned by running_sum > target. Why this step? We do not stop at the first hit — Cell E wants all solutions, so we keep the counter running and continue the DFS.
2. Backtrack: include 2, exclude 4, then include 6 → sum 8 > 6 ✗ pruned; include 8 → 10 ✗. No solution on this branch. Why this step? Having recorded {2,4}, the undo step restores running_sum back to 2 so we can honestly explore the exclude-4 sibling — showing why the "undo" is what keeps sibling branches correct.
3. Exclude 2: include 4 → 4, include 6 → 10 ✗ … ; the single-element {6} → sum 6 ✓ → record {6}. Why this step? Excluding 2 opens the branch where 6 alone hits the target.
4. All other branches overshoot or undershoot.

Verify: The solutions are {2,4} and {6} → 2 subsets. ({2,4}→6 ✓, {6}→6 ✓; no other subset of [2,4,6,8] sums to 6.) Answer: 2.

---

Ex 6 — Cell F: permutations, pruning does NOTHING (worst case)

Steps:

1. State = the permutation built so far; candidates = unused elements. is_valid = "not already used" — but that's the only rule, and it never lets us prune a partial prefix as hopeless (every partial permutation extends to a full one). Why this step? This is the adversarial case for pruning: no dead-ends before the leaves. See Permutations-and-Combinations.
2. Depth 0: 3 choices. Depth 1: 2 remaining. Depth 2: 1 remaining. Every path reaches a valid leaf. Why this step? We enumerate the branching to show the tree is complete — no prune ever fires. Why no prefix is ever hopeless: the only constraint is "distinct elements", and any prefix of distinct elements can always be finished by appending the remaining (still-distinct) elements in some order. There is no partial arrangement from which a valid completion is impossible, so nothing can be cut early.

Verify: number of permutations of 3 distinct items $=3!=6$, and the number of leaves visited equals 6 — pruning saved nothing. This is why the parent note warns: worst-case Big-O stays $O(b^d)$. See Time-Complexity. Answer: 6 permutations.

---

Ex 7 — Cell G: pruning does EVERYTHING (bound cuts at root)

Steps:

1. running_sum > target prune: the moment we include any element, sum $\ge 10>5$ → that "include" branch dies immediately. Why this step? Every "include" child is instantly pruned; only the all-exclude path survives.
2. The empty subset gives sum 0, which is not 5 → no solution recorded.

Recall Exact node count for Ex 7 (include-first, prune when sum>target)

Walk the include/exclude tree of [10,12,14]:

• Root (sum 0) — node 1.
• Include 10 → sum 10 > 5 → pruned, child not created.
• Exclude 10 → sum 0 — node 2.
  • Include 12 → sum 12 > 5 → pruned.
  • Exclude 12 → sum 0 — node 3.
    • Include 14 → sum 14 > 5 → pruned.
    • Exclude 14 → sum 0, leaf — node 4. So exactly 4 nodes are visited (the full unpruned tree would have $1+2+4+8=15$), and 0 leaves hit target 5.

Verify: No nonempty subset $\le 5$; empty subset sums to 0 ≠ 5 → 0 subsets, and exactly 4 nodes are visited instead of $2^3=8$ leaves / 15 total nodes. Answer: 0 subsets, 4 nodes.

---

Ex 8 — Cell H: real-world word problem (task assignment)

Translate to backtracking:

• Candidates at worker r = jobs not yet assigned.
• is_valid = the forbidden-pair rules: reject W2↔A, reject W3↔C.

Steps (assign in order W1, W2, W3):

1. W1 = A. Then W2 ∈ {B,C}, W3 gets the last.
   • W2 = B → W3 = C ✗ (W3 can't do C) → dead end, backtrack.
   • W2 = C → W3 = B ✓ → record (A,C,B). Why this step? The ban on W3–C prunes the (A,B,·) branch before finishing.
2. W1 = B. W2 ∈ {A,C}; W2=A ✗ (ban) pruned. W2 = C → W3 = A ✓ → record (B,C,A). Why this step? The W2–A ban prunes a whole subtree at depth 1.
3. W1 = C. W2 ∈ {A,B}; W2=A ✗ pruned. W2 = B → W3 = A ✓ → record (C,B,A).

Verify: valid assignments = (A,C,B), (B,C,A), (C,B,A) → 3 assignments. Cross-check by brute force: of the 6 permutations, we remove any with W2=A or W3=C, leaving exactly these three. Answer: 3.

---

Ex 9 — Cell I: exam twist — count the NODES visited

Steps — walk the tree, marking pruned children (a pruned child is not created, so not counted):

1. Root (sum 0). node 1.
2. Include 3 (sum 3) — node 2.
   • Include 3 (sum 6) — node 3. Include 3 (sum 9 > 6 → pruned, child not created). Exclude 3 (sum 6, leaf) — node 4.
   • Exclude 3 (sum 3) — node 5. Include 3 (sum 6, leaf) — node 6. Exclude 3 (sum 3, leaf) — node 7.
3. Exclude 3 (sum 0) — node 8.
   • Include 3 (sum 3) — node 9. Include 3 (sum 6, leaf) — node 10. Exclude 3 (leaf) — node 11.
   • Exclude 3 (sum 0) — node 12. Include 3 (leaf) — node 13. Exclude 3 (empty subset, leaf) — node 14. Why this step? Only the two branches that would push sum to 9 are cut; everywhere else running_sum ≤ 6 so nothing else prunes.

Verify: Full tree = 15 nodes; exactly 1 node is pruned (the sum-9 child under node 3), leaving 14 nodes visited. The subsets recorded (sum exactly 6) are {3,3} chosen in several index-combinations — here 3 leaves hit sum 6 (nodes 3, 6, 10). Answer: 14 nodes visited, 3 successful leaves.

---

Ex 10 — Cell J: find ONE solution and stop immediately

Steps:

1. Include 2 (sum 2). Include 4 (sum 6) ✓ → this is a solution → return true. Why this step? Include-first order reaches {2,4} before ever considering {6}; the first hit wins.
2. That true propagates straight back to the root — the "exclude 2" half of the tree (which contained {6}) is never explored. Why this step? Short-circuiting is the whole point of Cell J: we spent effort only on the path to the first solution.

Verify: The first subset found is {2,4} (sum 6 ✓). It is reached by two "include" decisions, so the search touches only the leftmost spine — far fewer nodes than Ex 5's full enumeration. Answer: {2,4}, found on the first successful leaf.

---

The matrix, filled

Recall Which example covered which cell?

A (solution after backtracks) → Ex 1 · B (no solution) → Ex 2 · C (empty input) → Ex 3 · D (impossible target, prune at root) → Ex 4 · E (count all) → Ex 5 · F (pruning useless, worst case) → Ex 6 · G (pruning total) → Ex 7 · H (word problem) → Ex 8 · I (count nodes) → Ex 9 · J (find one, stop) → Ex 10.

Recall Self-test

Subset-sum [2,4,6,8] target 6 — how many subsets? ::: 2 — {2,4} and {6}. N-Queens n=3 — how many solutions? ::: 0. N-Queens n=4 — how many solutions? ::: 2. Subsets of the empty list — how many? ::: 1 (the empty set). Why did permutations of [1,2,3] prune nothing? ::: No partial prefix is ever hopeless — every prefix extends to a valid full permutation, so no subtree is cut. Task assignment with bans W2≠A, W3≠C — valid count? ::: 3. What does $b$ and $d$ mean here? ::: $b$ = branching factor (children per node), $d$ = depth (decisions per full solution); tree has up to $b^d$ leaves. Find-one vs find-all — what changes in the code? ::: Find-one returns a boolean and short-circuits (returns up the recursion on first hit); find-all keeps recursing and collects into a list.

---

Connections

• Parent: Backtracking (Hinglish) — the core template these examples drill.
• N-Queens — Ex 1, Ex 2 are its n=4 and n=3 instances.
• Permutations-and-Combinations — Ex 6's counting.
• Branch-and-Bound — Ex 4, Ex 7 use its "can this ceiling reach the target?" bound.
• Recursion · Depth-First-Search — the traversal machinery; Ex 10's short-circuit contrasts with full DFS.
• Time-Complexity — why pruning helps average, not worst case (Ex 6); defines the $b^d$ growth.
• Sudoku-Solver · Dynamic-Programming — where these same cells reappear.