--- title: "Backtracking: Subsets, Permutations & Combinations" module: Backtracking & Search moduleNumber: 9 lessonNumber: 1 order: 901 summary: | Backtracking builds a solution one choice at a time and abandons a partial solution the moment it cannot be completed, exploring a state-space tree by depth-first search. We meet the universal choose/explore/un-choose template, derive the canonical enumerations — subsets ($2^n$), permutations ($n!$), and combinations ($\binom{n}{k}$) — handle duplicate elements by skipping equal siblings, and see how pruning turns an exponential search into a tractable one. topics: [Backtracking] sources: - book: Skiena ref: "§7 — Combinatorial Search and Heuristic Methods" - book: Erickson ref: "Ch. — Backtracking" - book: CLRS ref: "Ch. — Exhaustive Search" practice: - title: 'Subsets' slug: subsets difficulty: Medium - title: 'Permutations' slug: permutations difficulty: Medium - title: 'Combinations' slug: combinations difficulty: Medium - title: 'Combination Sum' slug: combination-sum difficulty: Medium - title: 'Generate Parentheses' slug: generate-parentheses difficulty: Medium --- [Dynamic programming](/algorithms/dynamic-programming/principles), which closed the previous module, works when a problem has _overlapping subproblems_ we can tabulate. But a great many problems ask us instead to **enumerate or search a combinatorial space**: list every subset, every permutation, every way to place eight queens, every assignment satisfying a formula. These spaces are exponential, so we cannot afford to materialize them, yet we can traverse them selectively. **Backtracking** is the disciplined depth-first walk of such a space: it builds a candidate solution one decision at a time and **abandons** a partial candidate the instant it proves it cannot be extended to a valid complete one.[^erickson-bt] This act of abandonment, the _backtrack_, is what separates a directed search from blind brute force. This lesson opens the module by establishing the paradigm and instantiating it on the three enumerations every later technique builds on (subsets, permutations, and combinations) together with the two ideas that make backtracking _fast_ in practice: deduplication of equal choices and **pruning** of infeasible subtrees. ## The paradigm: choose, explore, un-choose Think of a solution as a sequence of decisions. At each step we have a **partial solution** and a set of **valid choices** to extend it. We pick one choice, recurse to extend further, and then **undo** that choice before trying the next one. The recursion thus traverses a **state-space tree** (also called a _decision tree_ or _choice tree_): the root is the empty partial solution, each edge is one choice, each node is the partial solution accumulated so far, and the leaves are complete candidates.[^skiena-bt] The walk is depth-first. > **Remark (The backtracking template).** To enumerate solutions, maintain a mutable > `partial`. At each node: if `partial` is _complete_, record it; otherwise, for > each _valid_ next choice — **choose** it (push onto `partial`), **explore** > (recurse), then **un-choose** it (pop), restoring `partial` exactly as it was. > Abandon a branch early whenever `partial` can no longer reach a valid solution. The un-choose step is what lets a single mutable buffer serve the entire tree: by the time control returns from a child, the buffer is byte-for-byte what it was before we descended, so the next sibling starts from a clean slate. $$ % caption: One mutable buffer across a node: \textbf{choose} pushes $c$, \textbf{explore} % recurses, \textbf{un-choose} pops — restoring the buffer exactly so the next % sibling starts clean \begin{tikzpicture}[ >=stealth, font=\small, slot/.style={draw, minimum size=7mm, inner sep=1pt, font=\small}, newslot/.style={draw=acc, very thick, minimum size=7mm, inner sep=1pt, font=\small}, stage/.style={draw=none, font=\scriptsize, align=center}, reslot/.style={draw, dashed, minimum size=7mm, inner sep=1pt, font=\small}] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-1.5,1.3) rectangle (12.6,-2.0); % stage 1: before \node[stage] at (0.7,0.95) {before}; \node[slot] at (0,0) {$x$}; \node[slot] at (0.7,0) {$y$}; \node[slot, fill=black!6] at (1.4,0) {}; \node[stage] at (0.7,-1.0) {partial $= xy$}; % arrow: choose \draw[->, acc, very thick] (2.1,0) -- node[above, draw=none, font=\footnotesize, acc] {\texttt{choose} $c$} (4.0,0); % stage 2: after push \node[stage] at (4.95,0.95) {explore}; \node[slot] at (4.2,0) {$x$}; \node[slot] at (4.9,0) {$y$}; \node[newslot] at (5.6,0) {$c$}; \node[stage] at (4.9,-1.0) {\texttt{recurse} on $xyc$}; % arrow: un-choose \draw[->, red!75!black, very thick] (6.3,0) -- node[above, draw=none, font=\footnotesize, text=red!75!black] {\texttt{un-choose}} (8.2,0); % stage 3: after pop (restored) \node[stage] at (9.05,0.95) {after}; \node[slot] at (8.4,0) {$x$}; \node[slot] at (9.1,0) {$y$}; \node[reslot] at (9.8,0) {}; % cleared-cell mark: drawn X (not $\times$, which garbles) \draw[red!75!black, thick] (9.62,-0.18) -- (9.98,0.18); \draw[red!75!black, thick] (9.62,0.18) -- (9.98,-0.18); \node[stage] at (9.1,-1.0) {partial $= xy$ again}; % note \node[draw=none, font=\scriptsize, align=left] at (11.6,0) {next\\ sibling\\ starts\\ clean}; \end{tikzpicture} $$ ```algorithm caption: $\textsc{Backtrack}(partial)$ — generic DFS over the state-space tree if $\textsc{IsComplete}(partial)$ then record a copy of $partial$ return for each $c \in \textsc{ValidChoices}(partial)$ do if $\textsc{Prune}(partial, c)$ then continue // prune $\textsc{Apply}(partial, c)$ // choose $\textsc{Backtrack}(partial)$ // explore $\textsc{Undo}(partial, c)$ // un-choose ``` Everything in this lesson is a specialization of this skeleton: the four primitives $\textsc{IsComplete}$, $\textsc{ValidChoices}$, $\textsc{Prune}$, and the choose/undo pair are all we ever change. ## Subsets: the power set in $2^n$ The cleanest decision tree is the **power set** of $\{a_0, \dots, a_{n-1}\}$. Each element faces one binary decision, _in_ the subset or _out_, so the tree is a perfect binary tree of depth $n$, and its $2^n$ leaves enumerate the $2^n$ subsets. This is the **include–exclude** recursion: ```algorithm caption: $\textsc{Subsets}(a, i, partial)$ — include/exclude each element if $i = n$ then record a copy of $partial$ return $\textsc{Subsets}(a, i+1, partial)$ // exclude $a_i$ $partial.\text{push}(a_i)$ // include $a_i$ $\textsc{Subsets}(a, i+1, partial)$ // explore $partial.\text{pop}()$ // un-choose ``` $$ % caption: DFS over the include/exclude choice tree for subsets of $\{1,2,3\}$. % Each level decides one element in or out; edge $-i$ excludes $a_i$, $+i$ includes it. \begin{tikzpicture}[ every node/.style={draw, circle, minimum size=7mm, inner sep=1pt, font=\small}, level distance=13mm, level 1/.style={sibling distance=34mm}, level 2/.style={sibling distance=17mm}, level 3/.style={sibling distance=9mm}, edgelbl/.style={draw=none, font=\scriptsize, fill=none}, leaf/.style={draw=none, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node {[\,]} child {node {[\,]} child {node {[\,]} child {node[leaf] {[\,]}} child {node[leaf] {[3]}} edge from parent node[edgelbl, left] {out 2}} child {node {[2]} child {node[leaf] {[2]}} child {node[leaf] {[2 3]}} edge from parent node[edgelbl, right] {in 2}} edge from parent node[edgelbl, left] {out 1}} child {node[draw=acc, text=acc] {[1]} child {node {[1]} child {node[leaf] {[1]}} child {node[leaf] {[1 3]}} edge from parent node[edgelbl, left] {out 2}} child {node[draw=acc, text=acc] {[1 2]} child {node[leaf] {[1 2]}} child {node[leaf, text=acc] {[1 2 3]}} edge from parent[draw=acc] node[edgelbl, right] {in 2}} edge from parent[draw=acc] node[edgelbl, right] {in 1}}; \end{tikzpicture} $$ An equivalent and often handier formulation uses a **start index** so that _every node_, not only the leaves, is a valid subset. We loop over choices $a_i, a_{i+1}, \dots$, and each recursion only ever looks _forward_ from the chosen index, which guarantees we generate each subset once, in lexicographic order of indices: ```algorithm caption: $\textsc{Subsets}(a, start, partial)$ — emit every node, advance start record a copy of $partial$ // every node is a subset for $i \gets start$ to $n-1$ do $partial.\text{push}(a_i)$ // choose $a_i$ $\textsc{Subsets}(a, i+1, partial)$ // forward only $partial.\text{pop}()$ // un-choose ``` Advancing the start index to $i+1$ in the recursive call is what stops the same subset $\{1,2\}$ from being generated twice, once as $1$-then-$2$ and once as $2$-then-$1$: an element earlier in the array is never chosen _after_ a later one. Both formulations do $O(2^n)$ recursive calls and spend $O(n)$ to copy each emitted subset, for $\Theta(n \cdot 2^n)$ total, unavoidable, since the output itself has that size. ::impl{algo="subsets#subsets_include_exclude+subsets"} ## Permutations: $n!$ orderings A **permutation** uses every element, so completeness is "all $n$ chosen," and the valid choices at each step are the elements _not yet used_. We track membership with a boolean `used[]` array; the branching factor shrinks from $n$ at the root to $n-1$, then $n-2$, giving exactly $n \cdot (n-1) \cdots 1 = n!$ leaves. ```algorithm caption: $\textsc{Permute}(a, used, partial)$ — pick an unused element each step if $|partial| = n$ then record a copy of $partial$ return for $i \gets 0$ to $n-1$ do if $used[i]$ then continue // not a valid choice $used[i] \gets \text{true}$; $partial.\text{push}(a_i)$ // choose $\textsc{Permute}(a, used, partial)$ // explore $partial.\text{pop}()$; $used[i] \gets \text{false}$ // un-choose ``` An alternative avoids the auxiliary array by **swapping in place**: to permute $a[k..n{-}1]$, swap each candidate into position $k$, recurse on $a[k{+}1..n{-}1]$, then swap it back: the swap-back _is_ the un-choose. Either way the work is $\Theta(n \cdot n!)$, dominated by emitting $n!$ permutations of length $n$. $$ % caption: Permutation state-space tree for $\{1,2,3\}$ — the branching shrinks % $3\to2\to1$ as elements are consumed, giving $3!=6$ leaves \begin{tikzpicture}[ every node/.style={draw, circle, minimum size=6mm, inner sep=1pt, font=\small}, level distance=13mm, level 1/.style={sibling distance=30mm}, level 2/.style={sibling distance=14mm}, level 3/.style={sibling distance=10mm}, edgelbl/.style={draw=none, font=\scriptsize, fill=none}, leaf/.style={draw=none, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node {[\,]} child {node {$1$} child {node {$2$} child {node[leaf] {$123$} edge from parent node[edgelbl,right]{$3$}} edge from parent node[edgelbl,left]{$2$}} child {node {$3$} child {node[leaf] {$132$} edge from parent node[edgelbl,right]{$2$}} edge from parent node[edgelbl,right]{$3$}} edge from parent node[edgelbl,left]{$1$}} child {node[draw=acc,text=acc] {$2$} child {node {$1$} child {node[leaf] {$213$} edge from parent node[edgelbl,left]{$3$}} edge from parent node[edgelbl,left]{$1$}} child {node[draw=acc,text=acc] {$3$} child {node[leaf,draw=acc,text=acc] {$231$} edge from parent[draw=acc] node[edgelbl,right]{$1$}} edge from parent[draw=acc] node[edgelbl,right]{$3$}} edge from parent[draw=acc] node[edgelbl,left]{$2$}} child {node {$3$} child {node {$1$} child {node[leaf] {$312$} edge from parent node[edgelbl,left]{$2$}} edge from parent node[edgelbl,left]{$1$}} child {node {$2$} child {node[leaf] {$321$} edge from parent node[edgelbl,right]{$1$}} edge from parent node[edgelbl,right]{$2$}} edge from parent node[edgelbl,right]{$3$}}; \end{tikzpicture} $$ Each root-to-leaf path consumes every element exactly once; the accented path (root $\to 2 \to 3 \to 1$) builds the permutation $231$. The fan-out is $3$ at the root, $2$ at depth one, and $1$ at depth two, so the leaf count is the falling product $3 \cdot 2 \cdot 1 = 3!$. ::impl{algo="permutations"} ## Combinations: $\binom{n}{k}$ with a start index A **combination** is a subset of a _fixed size_ $k$ where order does not matter. We want $\{1,3\}$ but not also $\{3,1\}$, so we reuse the **start-index** trick from subsets, which generates each combination exactly once by only ever choosing forward. Completeness is now "we have collected $k$ elements." ```algorithm caption: $\textsc{Combine}(n, k, start, partial)$ — choose $k$ in increasing order if $|partial| = k$ then record a copy of $partial$ return for $i \gets start$ to $n$ do $partial.\text{push}(i)$ // choose $i$ $\textsc{Combine}(n, k, i+1, partial)$ // forward only $partial.\text{pop}()$ // un-choose ``` The start index does the combinatorial bookkeeping: because the chosen indices strictly increase along any root-to-leaf path, each $k$-subset corresponds to exactly one path, and we enumerate all $\binom{n}{k}$ of them with no duplicates. This is the _same idea_ as the start-index subset enumerator: a combination is simply a subset enumeration cut off at depth $k$. ::impl{algo="combinations"} ## Handling duplicates: skip equal siblings When the input multiset contains repeated values, say $[1,2,2]$, the naive enumerator emits the same combination twice, because the two $2$s are _distinguishable by position but identical in value_. The standard fix is to **sort the array, then at each level skip a choice equal to the one just tried at the same depth.** > **Remark (Deduplication rule).** With $a$ sorted, inside the loop > `for i = start to n-1`: > $$\textbf{if } i > start \textbf{ and } a_i = a_{i-1} \textbf{ then continue.}$$ The condition $i > start$ carries the logic. The _first_ occurrence of a value at a given level (when $i = start$) is always allowed; we only skip _subsequent_ equal values **at the same depth**. > **Claim (skipping equal siblings loses no solution).** Discarding every sibling > branch after the first that chooses a given value at a level enumerates each > distinct solution exactly once. This is a [soundness](/algorithms/foundations/what-is-an-algorithm) claim about the prune: a pruning rule is _sound_ when it never discards a branch that contains a solution we have not already found elsewhere, so a sound prune keeps the search [complete](/algorithms/foundations/what-is-an-algorithm) — every distinct solution is still reported. > **Proof (soundness of the dedup prune).** Two sibling branches at the same depth that choose equal values > $a_i = a_{i-1}$ extend the _same_ `partial` by the _same_ value and then range > over the _same_ forward choices (both recurse with the same `start = i+1` on > equal suffixes), so they root _identical subtrees_ with identical completion > sets. Keeping only the first sibling therefore drops exact duplicates while > losing no distinct solution. $\qed$ The rule skips equal _siblings_, not equal _ancestors_: choosing $a_{i-1}$ then descending and choosing $a_i = a_{i-1}$ is legitimate (it uses _both_ copies), and there $i = start$ so the guard does not fire. $$ % caption: Sorted $[1,2,2]$: the second equal sibling at a level ($i>start,\ a_i=a_{i-1}$) % is skipped, dropping a duplicate subtree (dashed, red); ancestor reuse % $\{2,2\}$ survives \begin{tikzpicture}[ every node/.style={draw, minimum size=6mm, inner sep=3pt, font=\small}, level distance=14mm, level 1/.style={sibling distance=30mm}, level 2/.style={sibling distance=15mm}, edgelbl/.style={draw=none, font=\scriptsize, fill=white, inner sep=1.5pt}, skip/.style={draw=red!70, dashed, text=red!70}, edge from parent/.style={draw, ->, >=stealth}] \definecolor{acc}{HTML}{2348F2} \node {[\,]} child {node {[1]} child {node {[1 2]} edge from parent node[edgelbl,left]{$a_1$}} child {node[skip] {[1 2] dup} edge from parent[draw=red!70,dashed] node[edgelbl,right]{$a_2$}} edge from parent node[edgelbl,left]{$a_0{=}1$}} child {node {[2]} child {node {[2 2]} edge from parent node[edgelbl,right]{$a_2$}} edge from parent node[edgelbl,left]{$a_1{=}2$}} child {node[skip] {[2] dup} edge from parent[draw=red!70,dashed] node[edgelbl,right]{$a_2{=}2$}}; \end{tikzpicture} $$ At the root, $a_2{=}2$ repeats sibling $a_1{=}2$ (here $i>start$), so its whole subtree is pruned as a duplicate. Inside the $\{1\}$ branch the same guard fires, pruning $\{1,2\}'$. But descending from $\{2\}$ to $\{2,2\}$ is _ancestor_ reuse, not a sibling repeat — there $i=start$, the guard does not fire, and both copies of $2$ are legitimately used. This same machinery distinguishes two classic problems. In **Combination Sum**, each number may be reused unboundedly, so after choosing $a_i$ we recurse with `start = i` (do **not** advance); staying on the same element keeps it available. In **Combination Sum II**, each input number may be used at most once _and_ duplicates exist, so we recurse with `start = i+1` (advance) and apply the equal-sibling skip above to avoid duplicate combinations. $$ % caption: The one-line difference: reuse-allowed recurses with $start{=}i$ (stay), % use-once recurses with $start{=}i{+}1$ (advance) \begin{tikzpicture}[ >=stealth, font=\small, arr/.style={draw, minimum size=6mm, inner sep=1pt, font=\small}, pick/.style={draw=acc, very thick, minimum size=6mm, inner sep=1pt, font=\small}, ttl/.style={draw=none, font=\footnotesize, acc}, lbl/.style={draw=none, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-0.9,1.55) rectangle (10.6,-2.5); % ---- left: reuse allowed, start = i ---- \node[ttl] at (1.95,1.25) {reuse allowed: \texttt{start = i}}; \foreach \v/\x in {a/0, b/0.7, c/1.4, d/2.1} \node[arr] at (\x,0) {$\v$}; \node[pick] at (1.4,0) {$c$}; % stay-pointer: next call may pick c again (loop back to same cell) \draw[->, acc] (1.15,-0.45) .. controls (0.6,-1.1) and (1.4,-1.15) .. (1.4,-0.45); \node[lbl, acc] at (2.85,-1.05) {next \texttt{start = i}}; \node[lbl] at (1.95,-1.75) {$c$ stays in range: can rep\/eat}; % ---- right: use once, start = i+1 ---- \node[ttl] at (7.65,1.25) {use once: \texttt{start = i+1}}; \foreach \v/\x in {a/5.7, b/6.4, c/7.1, d/7.8} \node[arr] at (\x,0) {$\v$}; \node[pick] at (7.1,0) {$c$}; % advance-pointer: next call starts after c \draw[->, acc] (7.45,-0.45) -- (7.8,-0.95); \node[lbl, acc] at (8.75,-1.05) {next \texttt{start = i+1}}; \node[lbl] at (7.65,-1.7) {$c$ excluded: used at most once}; \end{tikzpicture} $$ ::impl{algo="subsets#subsets_with_duplicates"} ## Pruning: kill infeasible subtrees early Everything so far enumerates _all_ of a space. Backtracking becomes useful when the problem constrains the answer, because then we can **prune**: refuse to descend into a subtree the moment we can prove it contains no solution. Pruning prunes _whole subtrees_, so a single early cut can save exponentially many leaves. A prune is **sound** precisely when it only ever cuts subtrees that provably hold no solution; both cuts below qualify, so the search stays **complete** — no real solution is lost. Take **Combination Sum** with a target $T$ over sorted positive numbers. Two prunes apply at the point we consider extending `partial` (current sum $s$) by $a_i$: - **Over-target cut.** If $s + a_i > T$, this choice overshoots; and since the array is sorted ascending, _every later_ $a_j \ge a_i$ overshoots too, so we `break` out of the entire loop, not merely `continue`. - **Reachability cut** (a general lower-bound prune). If even the smallest remaining additions cannot reach $T$, abandon the branch. $$ % caption: Pruning kills infeasible subtrees early (target $T=5$, choices $\{2,3,4\}$) \begin{tikzpicture}[ every node/.style={draw, minimum size=7mm, inner sep=3pt, font=\small}, level distance=14mm, level 1/.style={sibling distance=30mm}, level 2/.style={sibling distance=16mm}, edgelbl/.style={draw=none, font=\scriptsize}, dead/.style={draw=red!75!black, dashed, text=red!75!black}, edge from parent/.style={draw, ->, >=stealth}] \definecolor{acc}{HTML}{2348F2} \node[draw=acc, text=acc] {$s=0$} child {node[draw=acc, text=acc] {$s=2$} child {node[dead] (d6) {$s=6$} edge from parent[draw=red!75!black, dashed] node[edgelbl, left] {$+4$}} child {node[draw=acc, text=acc] (live) {$s=5$} edge from parent[draw=acc] node[edgelbl, right] {$+3$}} edge from parent[draw=acc] node[edgelbl, left] {$+2$}} child {node {$s=3$} child {node[dead] (d7) {$s=7$} edge from parent[draw=red!75!black, dashed] node[edgelbl, right] {$+4$}} edge from parent node[edgelbl, right] {$+3$}} child {node {$s=4$} child {node[dead] (d8) {$s=8$} edge from parent[draw=red!75!black, dashed] node[edgelbl, right] {$+4$}} edge from parent node[edgelbl, right] {$+4$}}; % drawn X marks on over-target (dead) nodes; check on the live solution \foreach \n in {d6,d7,d8} { \draw[red!75!black, thick] ([xshift=3.5mm,yshift=1.3mm]\n.east) -- ++(2.6mm,-2.6mm); \draw[red!75!black, thick] ([xshift=3.5mm,yshift=-1.3mm]\n.east) -- ++(2.6mm,2.6mm); } \draw[acc, thick] ([xshift=3.4mm,yshift=-0.4mm]live.east) -- ++(1.2mm,-1.6mm) -- ++(2.6mm,3.2mm); \end{tikzpicture} $$ Each branch reaching $s > 5$ (the dashed $\times$ nodes) is dropped without descending further; the blue path $0 \to 2 \to 5$ is the live solution $\{2,3\}$. Pruning determines the practical cost: a search that _looks_ exponential can run in milliseconds when the prune severs the bulk of the tree, while a poorly pruned search of the _same_ size is hopeless. This is why Skiena frames practical combinatorial search as "the art of pruning."[^skiena-bt] To see how much the prune saves, trace **Combination Sum** with target $T = 7$ on the sorted candidates $[2, 3, 6, 7]$, each reusable. The recursion carries the running sum $s$ and a start index; the over-target cut `break`s the loop the moment $s + a_i > T$ (safe because later candidates are only larger). | Path so far | $s$ | tries $a_i$ | outcome | | --- | --- | --- | --- | | $[\,]$ | 0 | $2$ | descend | | $[2]$ | 2 | $2$ | descend | | $[2,2]$ | 4 | $2$ | descend | | $[2,2,2]$ | 6 | $2\!:\!8{>}7$ | **break** (also $3,6,7$ skipped) | | $[2,2,3]$ | 7 | — | **record** $\{2,2,3\}$ | | $[2,3]$ | 5 | $3\!:\!8{>}7$ | **break** | | $[2,6]$ | 8 | overshoot at entry | pruned | | $[3]$ | 3 | $3$ | descend | | $[3,3]$ | 6 | $3\!:\!9{>}7$ | **break** | | $[7]$ | 7 | — | **record** $\{7\}$ | The two solutions $\{2,2,3\}$ and $\{7\}$ are found while the over-target `break` lops off every branch that would push $s$ past $7$ — the subtrees under $[2,2,2]$, $[2,6]$, $[3,3]$, and the whole $[6,\dots]$ region never materialize. Without the sorted-`break` prune the same search would blindly expand all of them before discovering they overshoot. ::impl{algo="combination_sum,generate_parentheses"} ## Complexity: the size of the explored tree There is no single formula for "backtracking complexity"; the running time is simply **the size of the state-space tree we actually explore**, times the work per node. For a _full_ enumeration this is the output size: $\Theta(n \cdot 2^n)$ for subsets, $\Theta(n \cdot n!)$ for permutations, $\Theta(k \binom{n}{k})$ for combinations. More generally the cost is $O(\#\text{nodes visited} \times \text{cost per node})$, and for problems whose answers we emit, it is bounded below by $\Omega(\#\text{solutions} \times \text{size of each})$: we cannot beat the cost of writing the output. > **Remark (The exponential-but-fast distinction).** Backtracking is **exponential in the > worst case** — adversarial inputs force exploration of nearly the whole tree. > But on typical inputs, pruning collapses the explored tree to a thin sliver of > its worst-case size, which is why backtracking solves $n$-queens, > Sudoku, and SAT instances far larger than $2^n$ counting would suggest.[^clrs-exhaustive] The lever is always the same: a tighter $\textsc{Prune}$ predicate cuts subtrees nearer the root, and the savings compound exponentially with the depth of the cut. ## From a 1965 method to modern industrial solvers The choose/explore/un-choose skeleton is the direct ancestor of some of the most widely used software in computing. **Naming the method.** The recursive-abandonment idea is old — the term _backtrack_ was coined by D. H. Lehmer in the 1950s — but Golomb and Baumert's 1965 paper "Backtrack Programming" was the first systematic treatment, and it already identified the two levers this lesson emphasizes: **preclusion** (pruning) and choosing which variable to branch on next.[^golomb] Every refinement since is a sharper answer to those two questions. **Dancing Links.** For exact-cover problems (Sudoku, pentomino tiling, $n$-queens), Knuth's **Algorithm X** with the **Dancing Links** data structure (2000) makes the choose/un-choose pair almost free: the constraint matrix is a doubly-linked mesh, covering a column unlinks its rows in $O(1)$, and _un_-covering relinks them by running the same pointer operations backward — the un-choose step made literal.[^dlx] It remains the fastest general exact-cover solver and the reason a Sudoku solves in microseconds. **SAT solvers.** Boolean satisfiability is backtracking's largest application. The **DPLL** algorithm (Davis, Putnam, Logemann, Loveland, 1962) is backtracking over truth assignments with **unit propagation** — a constraint-propagation prune. Its modern descendant, **CDCL** (conflict-driven clause learning), adds two ideas that transform the search: when a branch fails, it _analyzes the conflict_ to learn a new clause that prunes many future branches, and it **non-chronologically backjumps** past irrelevant decisions rather than backtracking one level at a time.[^cdcl] CDCL solvers routinely dispatch formulas with millions of variables, and are used in hardware verification, program analysis, and automated planning — all built on the recursion of this lesson. ## Takeaways - **Backtracking** is depth-first search of a **state-space tree**: build a partial solution incrementally, and **abandon** any branch that cannot reach a valid complete solution. - The universal template is **choose / explore / un-choose**: a single mutable buffer suffices because the undo step restores it before each sibling is tried. - **Subsets** ($2^n$) come from an include/exclude binary recursion or a forward-only **start index**; **permutations** ($n!$) from a `used[]` array or in-place swapping; **combinations** ($\binom{n}{k}$) from a start index that forces increasing choices so each set is generated once. - **Duplicates** are handled by sorting and skipping equal siblings at the same depth (`if i > start and a[i] == a[i-1] continue`), which drops identical subtrees without losing distinct solutions; **reuse-allowed** variants keep `start = i` instead of advancing. - **Pruning**, cutting infeasible or non-improving subtrees early (sum exceeds target, bound can't beat the best), is what separates exponential-but-fast from hopeless; one early cut saves an exponential subtree. - Running time is the **size of the explored tree** times per-node work: exponential in the worst case, but tamed to practicality by good pruning on typical inputs. [^erickson-bt]: **Erickson**, Ch. — Backtracking: incrementally constructing a solution and abandoning partial candidates that cannot be completed. [^skiena-bt]: **Skiena**, §7 — Combinatorial Search and Heuristic Methods: the state-space search tree and pruning as the core of efficient exhaustive search. [^clrs-exhaustive]: **CLRS**, Ch. — Exhaustive Search: backtracking explores only feasible extensions, exponential in the worst case but far smaller in practice. [^golomb]: **Golomb, S. W. & Baumert, L. D.** (1965), "Backtrack programming," _Journal of the ACM_ 12(4), 516–524 — the first systematic study of backtracking, naming preclusion (pruning) and variable ordering as the two levers of efficiency. [^dlx]: **Knuth, D. E.** (2000), "Dancing links," in _Millennium Perspectives in Computer Science_, 187–214 — Algorithm X with the doubly-linked Dancing Links structure making cover/uncover (choose/un-choose) $O(1)$ and reversible. [^cdcl]: **Marques-Silva, J. P. & Sakallah, K. A.** (1999), "GRASP: a search algorithm for propositional satisfiability," _IEEE Transactions on Computers_ 48(5), 506–521 — conflict-driven clause learning and non-chronological backjumping, extending the DPLL backtracking search (Davis, Logemann & Loveland, 1962) into modern industrial SAT solvers.