Subsets

The problem it solves

Produce every subset of a collection — the power set: for [1, 2, 3], all eight of ∅, [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Directly, this is test-case generation, feature-flag matrices, brute-force over small option spaces, and the inner loop of many “try every combination” solvers. Indirectly — and more importantly for interviews — it is the smallest complete backtracking problem: two branches, no constraints, no pruning, nothing to obscure the one discipline that every harder backtracking problem lives or dies by: choose, explore, un-choose.

Learn the discipline here, where the tree is tiny and every leaf is visible, and combination sum, subsets-with-duplicates, palindrome partitioning and N-queens become variations rather than new algorithms. That is why this page exists despite the algorithm fitting in eight lines: the eight lines are a load-bearing template.

The intuition — and where it breaks down

Stand before each element and ask the only question available: in or out? Two answers, n elements, every combination of answers is a distinct subset — 2ⁿ of them, an identity the first prediction prompt asks for before the tree grows. The recursion realises the questioning literally: at element i, first take the exclude branch and enumerate everything below it; then take the include branch — push the element onto a shared chosen list — and enumerate everything below that; then pop it back off.

That pop is the entire subject. The chosen list is one mutable object threaded through the whole tree. When the include-branch’s subtree finishes, the list must be restored to exactly what the parent’s other branches expect — and the pop does exactly that, undoing exactly one push. The player marks the current decision vector on the bars (chosen elements inked, excluded ghosted) so the restore is visible: watch the marks retreat as the recursion unwinds, level by level, always in reverse order of how they advanced. The “un-choose” annotation fires at each one because this is the habit to build: every mutation on the way down has a mirror on the way up.

Where the intuition breaks: “in or out” suggests the decisions are independent — and for plain subsets they are, which is why there is no pruning and no constraint check. The moment the problem adds a predicate (“subsets summing to k”, “no two adjacent”), the same tree grows an early-exit test at each node, and that — this tree plus pruning — is the general backtracking pattern. The clean version here is the control group.

Loading…

A walkthrough you can check

Enumerate subsets of [1, 2], exclude-branch first:

1. At element 1: exclude. At element 2: exclude. Bottom — record ∅.
2. Backtrack one level; include 2. Bottom — record [2]. Pop 2.
3. Backtrack to the top; include 1. At element 2: exclude. Bottom — [1].
4. Include 2. Bottom — [1, 2]. Pop 2, pop 1. Done: four subsets, 2².

Two things to verify in the player on the default four-element input. First, the order: subsets arrive grouped by their decision on element 0 — the entire exclude-world before the entire include-world — which is the tree structure made audible. Second, the restores: after the final leaf, every mark is gone and chosen is empty; the unit suite asserts this balance (chooses minus un-chooses = 0), because a single missing pop corrupts every subset after it — silently, which is what makes it the signature bug.

The invariant

At a node at depth i, chosen contains exactly the elements included among 0..i−1 on the current path — and nothing else. It holds at the root (empty list, no decisions). The exclude branch preserves it trivially; the include branch extends it by exactly its own element and — this is the load-bearing clause — removes exactly that element before returning. So when control returns to any node, the invariant it started with has been restored, and its next branch begins from a truthful state.

Correctness follows in both directions: every leaf’s snapshot is a genuine subset (the invariant says so at depth n), and every subset is reached (each of the 2ⁿ decision vectors corresponds to exactly one root-to-leaf path). No duplicates, no omissions, no bookkeeping beyond one list and the discipline of restoring it.

Complexity, derived

The tree has 2ⁿ leaves and 2ⁿ − 1 internal nodes: O(2ⁿ) nodes, O(1) work at each, plus O(n) to copy each subset out at its leaf — O(2ⁿ · n) time, and it cannot be otherwise: the output alone is 2ⁿ subsets averaging n/2 elements. Exponential cost is the problem’s nature, not the algorithm’s failure — a sentence worth saying in interviews before anyone asks. Space beyond the output: O(n) — the recursion depth and the shared list.

The counters panel shows the doubling directly: run the 3-, 4- and 5-element presets and watch the subsets counter land on 8, 16, 32. When a problem needs only the count of subsets with a property, this enumeration is usually the wrong tool — counting is a formula or a DP; enumeration is for when you must touch each one.

What people get wrong

• Pushing the live list into the output instead of a copy. Every recorded “subset” aliases the same object, which is empty when the recursion ends — the output is 2ⁿ references to nothing. The single most common bug in submitted solutions.
• The missing pop: one un-choose forgotten, every later subset polluted by a stowaway element. The balance assertion exists for this.
• Choosing before both branches: the exclude branch must run against the unmodified list; push-then-explore-both double-counts.
• Duplicates unhandled: with repeated input values, identical subsets emerge from different paths. Sort first, then skip an element equal to its predecessor unless the predecessor was taken.
• Recursing when the bitmask loop is cleaner: for flat enumeration, counting 0..2ⁿ−1 and reading bits is shorter and iterative. Know both; the recursion earns its keep when pruning enters.

Implementation notes

The recursive template is the one to internalise, verbatim: base case records a copy; exclude-recurse; push; include-recurse; pop. Every harder problem edits exactly one line of it — combination sum adds a running total and a prune; subsets-II adds the sorted-skip guard; partitioning changes what a “choice” is. Keeping the template rigid is what makes the variations safe.

The bitmask alternative deserves its paragraph: for mask in 0..2ⁿ−1, element i is in iff bit i is set. Same enumeration, no recursion, no restore discipline needed — the counter cannot forget to pop. Its limits: no natural pruning (you visit every mask), and n ≤ ~25 before the loop count hurts. The two versions correspond exactly — the recursion’s decision vector is the mask, drawn on the bars — and being able to translate between them on a whiteboard is a quiet but real signal.

For subsets in a fixed interesting order (by size, lexicographic), either sort the output or change the traversal: include-first yields larger subsets earlier; iterating masks by popcount groups by size. And when generating for a consumer that may stop early, prefer a generator/iterator shape — enumeration problems rarely need the whole power set in memory at once.

The follow-up questions

Why must every choose be un-chosen? One shared list serves the entire tree; the pop restores the parent’s exact state so sibling branches are independent. Skip one and the corruption is silent and cumulative.

How does the bitmask version relate? Bit i of a counter from 0 to 2ⁿ−1 is the in/out decision for element i — the same decision vectors the recursion walks, generated arithmetically. Same output, no stack, no restore bugs, no pruning hooks.

Subsets with duplicates? Sort; at each depth, skip a value equal to its predecessor when the predecessor was excluded. This collapses the duplicate paths without missing any distinct subset.

When is enumeration the wrong answer? When only a count or an optimum is needed — 2ⁿ is a formula and “best subset” is usually a DP (knapsack’s territory). Enumerate only when each subset must actually be produced or tested.