Backtracking: Subsets, Permutations & Combinations

Dynamic programming, 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 walk them cleverly. Backtracking is the disciplined depth-first walk of such a space: it builds a candidate solution one decision at a time and, crucially, abandons a partial candidate the instant it proves it cannot be extended to a valid complete one.¹ 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.² The walk is depth-first.

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.

Everything in this lesson is a specialization of this skeleton: the four primitives $\text{IsComplete}$, $\text{ValidChoices}$, $\text{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 are exactly the $2^n$ subsets. This is the include–exclude recursion:

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:

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.

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.

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+\mathrm{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$.

Each root-to-leaf path consumes every element exactly once; the accented path $\cdot \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!$.

Combinations: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 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.

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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 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$.

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.

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. Why does this dedup correctly? Two sibling branches that choose equal values would root identical subtrees, the same set of completions, so keeping only the first sibling drops the duplicate subtrees while losing no distinct solution. Note we skip 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.

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, killing $\{1,2{\}}^{\prime }$. But descending from $\{2\}$ to $\{2,2\}$ is ancestor reuse, not a sibling repeat — there $i=start$, the guard stays silent, 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.

Pruning: kill infeasible subtrees early

Everything so far enumerates all of a space. Backtracking earns its keep 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.

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.

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 does the heavy lifting: 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.²

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(\genfrac{}{}{0ex}{}{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.

The lever is always the same: a tighter $\text{Prune}$ predicate cuts subtrees nearer the root, and the savings compound exponentially with the depth of the cut.

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 ($\left(\genfrac{}{}{0ex}{}{n}{k}\right)$) 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.