Subsets (power set)
mediumIn or out, n times, giving 2ⁿ outcomes. Every subset corresponds to a bitmask, which is the bridge from backtracking to bitmask dynamic programming.
O(n × 2ⁿ)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How subsets (power set) works
Every subset is the result of n independent yes-or-no decisions: element 0 in or out, element 1 in or out, and so on. Two options taken n times gives 2ⁿ outcomes, so the power set of the default 4 elements has exactly 16 members. The recursion mirrors this - at element i it branches once for exclude and once for include, forming a full binary tree of depth n.
The choose-explore-undo skeleton appears here in its smallest form. Choosing is cur.push(a[i]), undoing is cur.pop(), and the exclude branch needs no state change at all. This engine takes the exclude branch first, so the empty set is recorded first and the full set last. There is nothing to prune - every leaf is a valid subset - so the tree is walked whole.
The same shape carries a family of problems. Add a size check and it generates combinations; add a running total with a cutoff and it is combination sum. And because each subset is exactly an n-bit mask - 1011 means take elements 0, 1, and 3 - counting from 0 to 2ⁿ − 1 enumerates the power set with no recursion, the bridge to bitmask dynamic programming.
Step by step
- Run [1, 2, 3]. The recursion dives down the all-exclude spine first: three leave-it-out decisions in a row, recording the empty set.
- Unwinding one level, element 3 flips to include - subset 3 is recorded. The undo pops it before the next branch.
- Element 2's include branch runs next: subset 2 arrives, then with 3 added on top of it, subset 2,3.
- The recursion returns to the root and finally includes element 1, repeating the whole pattern over the suffix: 1, then 1,3, then 1,2, then 1,2,3.
- Eight subsets total - exactly 2³ - in the order ∅, 3, 2, 23, 1, 13, 12, 123, each recorded as a copy of cur.
- Read the results against their bitmasks, one bit per element: 000 is ∅, 101 picks elements 0 and 2, 111 is the full set.
Complexity
| Worst case time | O(n × 2ⁿ) |
|---|---|
| Space | O(n) |
Reference implementation
Python
def subsets(a):
out, cur = [], []
def backtrack(i):
if i == len(a):
out.append(cur[:])
return
backtrack(i + 1) # exclude a[i]
cur.append(a[i]) # include a[i]
backtrack(i + 1)
cur.pop() # undo
backtrack(0)
return out
def subsets_bitmask(a):
"""The same 2^n subsets, no recursion."""
n = len(a)
return [[a[i] for i in range(n) if mask >> i & 1]
for mask in range(1 << n)]JavaScript
function subsets(a) {
const out = [], cur = [];
(function backtrack(i) {
if (i === a.length) { out.push([...cur]); return; }
backtrack(i + 1); // exclude
cur.push(a[i]);
backtrack(i + 1); // include
cur.pop();
})(0);
return out;
}
// Bitmask version - each of the 2^n masks *is* a subset.
const subsetsBitmask = (a) =>
Array.from({ length: 1 << a.length }, (_, m) =>
a.filter((_, i) => (m >> i) & 1));Worth noticing
One binary decision per element
In or out - that is the entire choice. n independent binary decisions give 2ⁿ outcomes, which is why the power set has exactly that many members and why the recursion tree is a perfect binary tree of depth n.
A bitmask *is* a subset
Mask 1011 means take elements 0, 1 and 3. Looping masks from 0 to 2ⁿ−1 enumerates every subset with no recursion at all - and makes subset-based dynamic programming possible.
The same shape as combinations and combination-sum
Add a size check and you get combinations; add a running total and a pruning condition and you get combination-sum. The include/exclude skeleton is the reusable part.
Common pitfalls
- Recording cur without copying. All 2ⁿ entries end up as references to one list that is empty again when the search finishes - push a copy.
- Forgetting cur.pop() after the include branch. The element leaks into every subset recorded later, and the output quietly contains wrong members.
- Confusing subsets with subarrays. Subarrays are contiguous slices - only n(n+1)/2 of them - while subsets ignore position entirely and number 2ⁿ.
- Dropping the empty set. It is a legitimate subset - the all-exclude branch - and recursion that starts by force-including an element loses it.
- Enumerating all 2ⁿ subsets when the problem only asks whether one exists. Subset-sum reachability is answered by dynamic programming in O(n × target), not by generation.
Where it is used
- Bitmask dynamic programming - Held-Karp for the travelling salesman and set-cover DPs iterate exactly these 2ⁿ subset masks as states.
- Feature and configuration sweeps, where every combination of n optional flags must be built or tested.
- Subset-sum style brute force - the 2ⁿ enumeration is the baseline the knapsack DP is measured against.
- LeetCode 78 verbatim, with combinations and combination sum as the immediate interview follow-ups sharing the skeleton.
Frequently asked questions
What is the time and space complexity of generating all subsets?
Time is O(n × 2ⁿ): there are 2ⁿ subsets and each copy costs up to O(n). The output itself has that size, so the bound cannot be improved. Working space beyond the output is O(n) - one shared cur list and a recursion stack n deep.
What is the difference between a subset and a combination?
A combination is a subset with its size fixed in advance: choosing 2 of [1, 2, 3] gives the C(3, 2) = 3 combinations 12, 13, 23. Subsets place no size constraint, so all sizes appear, and 2ⁿ equals the sum of C(n, k) over every k.
How does the bitmask version work?
Number the elements 0 to n − 1 and let bit i of a mask mean element i is in. Mask 1011 takes elements 0, 1, and 3. Counting masks from 0 to 2ⁿ − 1 visits every subset with a plain loop - no recursion, and the natural indexing for subset-based DP tables.
Why does the empty set count as a subset?
It is the outcome where every element chose out - the first result this engine records. A subset only requires that each of its members belong to the set, which the empty set satisfies vacuously. Dropping it leaves 2ⁿ − 1 and breaks the binary-decision counting.