Chapter 12 — Backtracking
Source:
src/main/kotlin/backtracking/andsrc/main/kotlin/array/Combinatorics/(plusstring/backtracking/)Master idea: backtracking is DFS with an undo button — explore a choice, recurse, and un-make the choice before trying the next one. It’s the right tool whenever the problem asks to enumerate all solutions of a combinatorial shape (subsets, permutations, partitions, placements).
Prerequisites: recursion, the DFS from Chapters 5/6, and the validity-checking sets from 10.4.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 12.1 | Subsets | positional include/exclude | $O(2^n)$ | → |
| 12.2 | Permutations | swap-based | $O(n!)$ | → |
| 12.3 | Generate Parentheses | balance-constrained | $O(\binom{2n}{n})$ | → |
| 12.4 | N-Queens | row-by-row placement | $O(n!)$ | → |
| 12.5 | Palindrome Partitioning | prefix pruning | $O(2^n)$ | → |
| 12.6 | Restore IP Addresses | segment-length pruning | $O(1)$ (fixed shape) | → |
| 12.7 | Sudoku Solver | cell-by-cell with validity | $O(9^{81})$ bound | → |
| 12.8 | Combination Sum | include/exclude with repetition | $O(2^t)$ | → | | 12.9 | Partition To K Equal Sum Subsets | subset-building backtracking | $O(k 2^n)$ | → | | 12.10 | Next Permutation | Narayana-Pandita | $O(n)$ | → | | 12.11 | Permutations II | per-frame seen-set dedupe | $O(n! n)$ | → | | 12.12 | Combinations | start-index backtracking | $O(C(n,k))$ | → | | 12.13 | Combination Sum III | k + sum gates with pruning | $O(C(9,k))$ | → | | 12.12 | Subsets II | sorted skip-duplicates | $O(2^n)$ | → | | 12.13 | N-Queens II | count-only backtracking | $O(n!)$ | → | | 12.14 | Word Search II | trie-pruned DFS | $O(mn4^L)$ | → | | 12.15 | Word Break II | memoized sentence enumeration | $O(2^n)$ | → | | 12.16 | Next Greater Element III | next-permutation digits | $O(log n)$ | → | | 12.17 | Strobogrammatic Number II | mirrored digit pairing | $O(5^{n/2})$ | → | | 12.19 | Closest Subsequence Sum | meet-in-the-middle | $O(2^{n/2}log)$ | → | | 12.20 | Max Length Of Concatenated String | bitmask backtracking | $O(2^n)$ | → |
The rest of the backtracking/ directories
src/main/kotlin/backtracking/ also holds: N-Queens II and N-Queens Optimized, Sudoku Solver (set-based variant), Partition To K Equal Sum Subsets, Path With Maximum Gold, Strobogrammatic Number II, Expression Add Operators (and optimized). array/Combinatorics/ adds Combinations, Subsets II (with duplicates), Permutations II (duplicates, backtracking + Narayana-Pandita), Next Permutation and its follow-ups. string/backtracking/ adds Word Break II and Word Square.
New pages are appended to the table above as they’re written.