Permutations and Subsets

Generating all subsets and all permutations are the two canonical backtracking problems. They share a template but differ in the "valid choices" predicate.

Subsets of $[a_1, a_2, \dots, a_n]$

For each element, decide: include or exclude. $2^n$ subsets total.

``` function subsets(i, current): if i == n: record(current) return subsets(i + 1, current) // exclude a_i current.push(a_i) subsets(i + 1, current) // include a_i current.pop() ```

Permutations of $[a_1, a_2, \dots, a_n]$

At each position, pick any not-yet-used element. $n!$ permutations.

``` function permute(current, remaining): if remaining is empty: record(current) return for each x in remaining: current.push(x) permute(current, remaining - {x}) current.pop() ```

With duplicates

Sort the input first. Then in subsets/permutations, skip a candidate at position $i$ if it equals the previous candidate AND that previous one was not used in the current partial solution. This guarantees each distinct combination is generated exactly once.

Combinations

"Choose $k$ of $n$" — same structure as subsets, but record only when current's size equals $k$. Prune branches that can't reach size $k$.

Generation order

Subsets generated by the above template appear in "increasing-index inclusion" order — useful when you want to process them lazily. Permutations come in lexicographic order if you keep the remaining set sorted; useful for "next permutation" problems.

Complexity

Subsets: $O(n \cdot 2^n)$ — $2^n$ subsets, each of average size $n/2$ to record. Permutations: $O(n \cdot n!)$. There's no asymptotic improvement possible — output dominates.