Week 08 — Backtracking: The Decision-Tree Discipline

Month 02, Week 04 (overall week 08) · 5 problems · 3 mediums + 1 medium-hard + 1 hard Theme: Search trees with explicit choose / recurse / un-choose. Pruning. Lexicographic vs free order. Symmetry breaking.

Why this week

Backtracking is the technique most candidates fake. They produce code that “works on the example” but breaks on duplicates, fails to deduplicate, mutates the wrong state, or — most commonly — forgets to un-choose. By the end of this week you will:

  • Have a single mental template you write reflexively: choose → recurse → un-choose.
  • Distinguish permutations (order matters, all elements used, used[] tracker) vs combinations (size-k subset, monotonically non-decreasing index) vs subsets (powerset, include/exclude at each index).
  • Prune at the FIRST opportunity instead of at the leaf — the difference between TLE and AC.
  • Handle the duplicate-input variant (sort + skip equal siblings) and the lex-order vs free-order distinction.
  • Solve a 2D grid backtracking problem (Word Search) with in-place visited-marking.
  • Build N-Queens — the canonical “symmetry-breaking + column/diagonal sets” problem — in under 20 minutes.

Problems

#ProblemDifficultyLCPattern signature
p36PermutationsMedium46used[] tracker; n! leaves
p37CombinationsMedium77start-index + k constraint; C(n,k) leaves
p38SubsetsMedium78include/exclude OR iterative powerset; 2^n leaves
p39Word SearchMedium-Hard79grid backtracking + in-place visited
p40N-QueensHard51column + diag + anti-diag sets; row-by-row

Daily schedule (5 days)

DayProblemStop at
Monp36 Permutationsclean template, both used[] and swap-in-place
Tuep37 Combinationsstart-index + early termination
Wedp38 Subsetsboth DFS and iterative
Thup39 Word Searchin-place visited, prune on first char mismatch
Frip40 N-Queensthree sets (col, diag, anti-diag) — O(n!) bounded by pruning

Readiness gate (end of week)

You can move to Week 9 when you can:

  • Write the universal backtracking template (choose / recurse / un-choose) in under 60 seconds.
  • Solve any “all permutations / all combinations / all subsets” variant in under 15 min.
  • Explain WHY used[] is needed for permutations but a start index suffices for combinations and subsets.
  • Handle the with-duplicates variant (sort() + if i > start and a[i] == a[i-1]: continue) without looking it up.
  • Word Search: explain why in-place visited-marking saves O(n·m·L) memory.
  • N-Queens: place the THREE attacker sets (col, diag = r + c, anti-diag = r - c) from memory.
  • Articulate the difference between “exponential time” (unavoidable for enumeration) vs “exponential WORK PER NODE” (pruning attacks the constant).

Anti-patterns to crush this week

  • Building strings via s + ch inside recursion (O(L) copy per call) — use a list and .append()/.pop().
  • Forgetting .pop() after .append() — your “current path” leaks into siblings.
  • Passing path[:] to recurse — works but wastes O(L) per call; the un-choose pattern is cleaner.
  • Returning a set of tuples to deduplicate at the end — should have pruned at the source via sort+skip.
  • Word Search marking visited with a separate set — use in-place sentinel ('#') and restore.
  • N-Queens validating a board column-by-column on each placement — use sets (O(1) lookup).
  • Re-counting len(path) == k in the loop instead of at function entry.

Sources

  • Sedgewick, Algorithms, Ch 2 (Backtracking).
  • CLRS, Ch 35 (Approximation), Ch 34 (NP) — for the “why exponential is fundamental” perspective.
  • Skiena, Algorithm Design Manual, Ch 9 (Combinatorial Search).