vault

Subsets

14 min read

Subsets

The power set of an n-element set is the collection of all 2^n subsets, including the empty set and the full set. The interview canon contains two power-set problems: (1) enumerate all 2^n subsets of an array of distinct elements (LeetCode 78) and (2) enumerate all distinct subsets of an array that may contain duplicates (LeetCode 90 Subsets II). Three primary implementation strategies recur: a backtracking schema with the include-or-exclude decision at each element (the cleanest formulation, also generalises to the duplicate-handling case via sort+level-skip), a bitmask iteration that runs for mask in range(1 << n) and reads off the subset corresponding to each integer’s bits (the simplest one-pass formulation, no recursion), and an iterative cascading construction that doubles the result list as each new element is processed (the most pedagogically illuminating). All three run in O(n · 2^n) time bounded by the output size; they differ in constants, code clarity, and incidental ordering. The duplicate-handling LC 90 uses the same sort the input + skip duplicates at the same recursion level pattern that recurs across Permutations and Combinations — a single idiom that solves all three sibling problems’ deduplication needs.

1. Intuition — Two Choices Per Element

For each of the n elements you have two and only two decisions: include it in the subset, or exclude it. Every distinct sequence of n such choices gives a distinct subset, and every subset arises from some sequence of choices. So there are exactly 2^n subsets, indexable by n-bit binary strings: bit i is 1 iff element i is included.

This is the secret of the bitmask approach: integers in [0, 2^n) are literally the index of the corresponding subset. mask = 0b0101 for input [a, b, c, d] (with a as bit 0, b as bit 1, etc.) corresponds to the subset {a, c} (bits 0 and 2 are set).

The backtracking and cascading approaches each express this binary-tree structure differently: backtracking walks the include/exclude decision tree node by node; cascading doubles a list.

2. Tiny Worked Example — Power Set of [1, 2, 3]

The 8 subsets, in three different orders:

Bitmask order (lex on bits)Backtracking include-then-exclude orderCascading order
000 = {}{} (or wherever the snapshot happens; typical lex)start: [ {} ]
001 = {1}{1}after 1: [ {}, {1} ]
010 = {2}{1, 2}after 2: [ {}, {1}, {2}, {1,2} ]
011 = {1, 2}{1, 2, 3}after 3: [ {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3} ]
100 = {3}{1, 3}
101 = {1, 3}{2}
110 = {2, 3}{2, 3}
111 = {1, 2, 3}{3}

All 8 subsets in all three orderings — same set, three different traversal orders. LC 78 accepts any order.

3. Pseudocode — Three Schemes

3.1 Backtracking (include/exclude per element)

subsets(nums):
    n := length(nums)
    results := []
    path := []

    define go(i):
        if i == n:
            append copy(path) to results
            return
        # exclude nums[i]
        go(i + 1)
        # include nums[i]
        push nums[i] onto path
        go(i + 1)
        pop path

    go(0)
    return results

3.2 Backtracking (start-index, snapshot at every node)

subsets_v2(nums):
    n := length(nums)
    results := []
    path := []

    define go(start):
        append copy(path) to results       # SNAPSHOT EVERY NODE, not just leaves
        for i := start to n - 1:
            push nums[i] onto path
            go(i + 1)
            pop path

    go(0)
    return results

This is structurally the same as the Combinations backtracker except the leaf-detection is gone — every node is a complete subset. The output count is the count of nodes in this tree, which is 2^n.

3.3 Bitmask Iteration (no recursion)

subsets_bitmask(nums):
    n := length(nums)
    results := []
    for mask := 0 to (1 << n) - 1:
        subset := []
        for i := 0 to n - 1:
            if (mask >> i) & 1:
                push nums[i] onto subset
        append subset to results
    return results

3.4 Iterative Cascading

subsets_iter(nums):
    results := [ [] ]
    for x in nums:
        new := []
        for s in results:
            push s onto new                          # without x
            push (s ++ [x]) onto new                 # with x
        results := new
    return results

4. Python Implementations

4.1 Backtracking, Start-Index (LC 78)

def subsets(nums: list[int]) -> list[list[int]]:
    results: list[list[int]] = []
    path: list[int] = []
 
    def go(start: int):
        results.append(path[:])             # snapshot at every node
        for i in range(start, len(nums)):
            path.append(nums[i])
            go(i + 1)
            path.pop()
 
    go(0)
    return results

For [1, 2, 3] this returns [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] — order of the §2 middle column.

4.2 Backtracking, Include-or-Exclude (alternate)

def subsets_inc_exc(nums: list[int]) -> list[list[int]]:
    results: list[list[int]] = []
    path: list[int] = []
 
    def go(i: int):
        if i == len(nums):
            results.append(path[:])
            return
        go(i + 1)                           # exclude nums[i]
        path.append(nums[i])                # include nums[i]
        go(i + 1)
        path.pop()                           # undo
 
    go(0)
    return results

This produces a slightly different traversal order (depending on exclude-first vs include-first) but the same 8 subsets. Pedagogically clearer for beginners — each call corresponds to one bit of decision.

4.3 Bitmask Iteration

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    results: list[list[int]] = []
    for mask in range(1 << n):              # 0 to 2^n - 1
        subset = [nums[i] for i in range(n) if (mask >> i) & 1]
        results.append(subset)
    return results

Walking through nums = [1, 2, 3]:

maskmask >> 0 & 1mask >> 1 & 1mask >> 2 & 1subset
0 = 000000[]
1 = 001100[1]
2 = 010010[2]
3 = 011110[1, 2]
4 = 100001[3]
5 = 101101[1, 3]
6 = 110011[2, 3]
7 = 111111[1, 2, 3]

This pattern — masks indexing subsets — is the gateway drug to Bitmask DP, where the state of a DP problem is a subset of “what we’ve already done.” Travelling Salesman on n ≤ 20 cities is the canonical example.

4.4 Iterative Cascading

def subsets_iter(nums: list[int]) -> list[list[int]]:
    results: list[list[int]] = [[]]
    for x in nums:
        results = results + [s + [x] for s in results]
    return results

The results = results + [s + [x] for s in results] line doubles the list at each step — first iteration: [ [] ] + [ [1] ] = [ [], [1] ]; second: [ [], [1] ] + [ [2], [1,2] ] = [ [], [1], [2], [1,2] ]; third: … and so on, ending with all 8 subsets.

This is “cascading” because each new element doubles the existing structure — the subset count goes 1 → 2 → 4 → 8 → … = 2^n. It’s also a one-line proof that |2^S| = 2 · |2^(S∖{x})|.

4.5 Subsets II (LC 90) — Duplicates in Input

When nums may have repeated values, sort + level-skip:

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)                     # 1) sort
    results, path = [], []
 
    def go(start: int):
        results.append(path[:])
        for i in range(start, len(nums)):
            # 2) skip duplicate at the same recursion level
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            go(i + 1)
            path.pop()
 
    go(0)
    return results

The skip predicate if i > start and nums[i] == nums[i - 1]: continue is identical to the Combinations LC 40 predicate, and the underlying logic is identical: among a run of equal values, fix the canonical ordering “use them left to right within a path.” Walking nums = [1, 2, 2]:

  • root start = 0: snapshot []. Loop i = 0, 1, 2.
    • i = 0, nums[0] = 1. No skip. Push 1, recurse start = 1.
      • snapshot [1]. Loop i = 1, 2.
        • i = 1, nums[1] = 2. No skip (i = start). Push 2, recurse start = 2.
          • snapshot [1, 2]. Loop i = 2. Push 2, recurse start = 3.
            • snapshot [1, 2, 2]. Empty loop. Return.
          • Pop. Return.
        • i = 2, nums[2] = 2, nums[1] = 2, i > start = 1 → skip.
    • Pop. Continue loop.
    • i = 1, nums[1] = 2. No skip (i = start = 0? No: i = 1, start = 0, so i > start; check equal: nums[1] = 2, nums[0] = 1, not equal → no skip). Push 2, recurse start = 2.
      • snapshot [2]. Loop i = 2. Push 2, recurse start = 3.
        • snapshot [2, 2].
      • Pop. Return.
    • Pop. Continue.
    • i = 2, nums[2] = 2, nums[1] = 2, i > start = 0 → skip.

Subsets emitted: [], [1], [1, 2], [1, 2, 2], [2], [2, 2] — six distinct, matching |{∅, {1}, {1,2}, {1,2,2}, {2}, {2,2}}| = 6 (which is what we expect for the multiset {1, 2, 2}: 3·2 = 6 distinct subsets).

The two skipped iterations would have produced [1, 2] (already seen via the first 2) and [2] (already seen) — the dedup is correct.

Subtle

The condition i > start (not i > 0) is the entire trick. Inside any recursive call, the loop starts at start; the first time we see a value at position start should never be skipped, only the second and later equal copies at the same call frame should. Replacing it with i > 0 would erroneously skip legitimate first-of-duplicate-group choices in subtrees deeper than the root.

5. Complexity

5.1 Counting Operations

Total subsets: 2^n. Each subset has on average n/2 elements; copying a subset costs O(n) (the snapshot copy in backtracking, the bit-extraction in bitmask, the list-concatenation in cascading). Total time: O(n · 2^n).

The exact count of comparisons / appends differs slightly across the three:

  • Backtracking: visits 2^n nodes; at each node, the snapshot is O(|path|) — total Σ |path_i| = n · 2^(n-1) (each element appears in half the subsets, contributing 2^(n-1) to the snapshot sum). Same O(n · 2^n) as a tighter bound.
  • Bitmask: 2^n masks × n bits per mask = n · 2^n. Exactly.
  • Cascading: at iteration i, doubles a list of size 2^(i-1). Total work Σ_{i=0..n-1} 2^i · i = O(n · 2^n). Same.
n2^nn · 2^n
10102410240
20~1M~20M
25~33M~830M
30~1B~32B

Realistically n ≤ 20 for full enumeration, n ≤ 25 if you’re patient. Beyond that, you typically need a different formulation: enumerate only subsets of bounded size (a Combinations problem), use Bitmask DP for an aggregate over subsets, or sample.

5.2 Space

  • Backtracking: O(n) recursion stack + O(n) path buffer = O(n) auxiliary, plus O(n · 2^n) output.
  • Bitmask: O(n) per subset construction = O(n) auxiliary, plus output.
  • Cascading: holds the full results array in memory at every step = O(n · 2^n) even before doubling.

Bitmask is the most memory-efficient; cascading is the worst. In practice the output dominates for any of them.

6. Power Set in Gray Code Order

A Gray code is an enumeration of 2^n binary strings such that consecutive strings differ in exactly one bit. Applied to subsets: consecutive subsets differ by one element added or removed. This is useful when the “subset value” you’re computing has a fast incremental update (e.g., XOR sum, sum, count) — instead of O(n) per subset to compute the value from scratch, you do O(1) per subset.

The standard Gray code for n = 3:

StepBinary GraySubset (bits)Diff from previous
0000{}—
1001{0}+0
2011{0, 1}+1
3010{1}-0
4110{1, 2}+2
5111{0, 1, 2}+0
6101{0, 2}-1
7100{2}-0

The simple formula for the i-th binary Gray code: gray(i) = i ^ (i >> 1).

def subsets_gray_code(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    results = []
    for i in range(1 << n):
        gray = i ^ (i >> 1)
        subset = [nums[j] for j in range(n) if (gray >> j) & 1]
        results.append(subset)
    return results

This produces all subsets of [1, 2, 3] as [[], [1], [1,2], [2], [2,3], [1,2,3], [1,3], [3]] — same 8 subsets, each adjacent pair differing by one element.

7. Diagram — The Power-Set Decision Tree

flowchart TD
    R["{} <br/>at depth 0, considering nums[0]=1"]
    R --> RE["{} <br/>exclude 1, depth 1, considering 2"]
    R --> RI["{1} <br/>include 1, depth 1, considering 2"]
    RE --> REE["{} (final) <br/>exclude 2, exclude 3"]
    RE --> REI["{2} <br/>include 2, exclude 3"]
    RE --> NE3["..."]
    RI --> RIE["{1} <br/>exclude 2, ..."]
    RI --> RII["{1,2} <br/>include 2, ..."]

    %% leaves at depth 3 — 8 of them
    REE --> L1["{} (leaf)"]
    REI --> L2["{2} (leaf)"]
    RIE --> L3["{1} (leaf)"]
    RII --> L4["{1,2} (leaf)"]

What this diagram shows. The power-set decision tree for [1, 2, 3] is a complete binary tree of depth 3 (the figure is abbreviated due to the 8-leaf full expansion). Each internal node represents a partial choice over the first d elements; each leaf is a complete subset. The left subtree always corresponds to “exclude” the current element, the right to “include”. The 2^n leaves are exactly the 2^n subsets, one for each binary path from root to leaf. The subsets_v2 start-index variant flattens this: it snapshots at every node (not just leaves), and pruning from the start index suppresses what would otherwise be visit-order duplication of the include/exclude tree’s subset content.

8. Pitfalls

  1. Snapshot order matters for the “include/exclude” backtracker. If you do go(i + 1); push; go(i + 1); pop, the recursion produces a specific order. Reversing to push; go(i + 1); pop; go(i + 1) gives a different order. LC 78 accepts any order, but if the problem requires a specific one, be deliberate.
  2. Snapshotting at the wrong place. In subsets_v2 the snapshot is at the top of go, not at a leaf check. Put it at the bottom and you’ll miss the empty subset. Put it inside the loop and you’ll duplicate.
  3. Wrong duplicate-skip predicate. if i > start and nums[i] == nums[i - 1]: continue, not if i > 0 and nums[i] == nums[i - 1]: continue. The latter erroneously skips legitimate first-occurrences inside subtrees. (The same trap as Combinations §8.2 and a cousin of the Permutations §9.3 trap.)
  4. Forgetting to sort before deduplication. The level-skip relies on equal values being adjacent. Without sorting, [2, 1, 2] won’t deduplicate.
  5. results.append(path) instead of results.append(path[:]). Same trap as in every other backtracking note. Without the snapshot copy, every recorded subset aliases the empty path at the end of the traversal.
  6. 1 << n overflow. For Python this isn’t a problem (arbitrary-precision integers), but in C/Java with n ≥ 32 you must use 1L << n or BigInteger. The bitmask approach is only tractable for n ≤ 30 or so even ignoring overflow.
  7. Recursion depth. With n around 1000 the include/exclude backtracker has depth n — Python’s default limit (1000) bites. Either lift the limit, switch to an iterative/bitmask approach (no recursion), or use cascading (no recursion).
  8. Cascading’s hidden quadratic. The naive results = results + [s + [x] for s in results] allocates O(2^n) Python objects every iteration. For very large n this is constant-factor slower than results.extend(...) with appropriate manipulation, but the asymptotic class doesn’t change.
  9. Mutable default argument. Standard Python gotcha; same as in Permutations and Combinations.
  10. Confusing subsets with subsequences with sublists/substrings. “Subset” in this problem is unordered ({1, 2} = {2, 1}); “subsequence” preserves order; “sublist/substring” is contiguous. The three are different problems with different counts (2^n, 2^n, n(n+1)/2 + 1).
  11. Treating subsets as a count problem. Counting subsets of a set is trivially 2^n. Counting subsets satisfying a property (e.g., summing to target) is a Subset Sum / Bitmask DP problem, not an enumeration problem.

9. Common Interview Problems

ProblemLeetCodeDifficultyVariation
Subsets78MediumDistinct elements, all 2^n subsets
Subsets II90MediumDuplicates in input, < 2^n distinct subsets via sort + level-skip
Letter Case Permutation784MediumSubset-style backtrack on character cases (each char: keep / flip case)
Gray Code89MediumGenerate subset masks in single-bit-difference order
Partition Equal Subset Sum416MediumSubset enumeration replaced by Bitmask DP for n ≤ 200
Maximum AND Sum of Array2172HardO(2^n) bitmask DP enumerating subset assignments
Combinations77MediumSubsets of fixed size k — see Combinations
Beautiful Arrangement II667MediumConstructive, related but not pure subset

10. Open Questions

  • When does Gray code subset enumeration beat lex-order? Mostly when the “value” of each subset has an O(1) incremental update under add-one / remove-one. For arbitrary subset functions where computation is O(n) per subset anyway, Gray code is no faster.
  • Knuth 4A §7.2.1.2 catalogs subset-generation algorithms (binary lex, Gray, balanced-Gray, etc.). Are any others tested in interviews? Anecdotally: no.
  • How does Subsets II’s complexity relate to the multiset’s structure? With multiplicities m_1, m_2, ..., m_k, the number of distinct subsets is Π_i (m_i + 1), which is at most 2^n and is reached only when all m_i = 1 (all distinct). For [1, 2, 2] it’s 2 · 3 = 6. The skip mechanism prunes the recursion to exactly this number of leaves.

11. See Also

Graph View

Backlinks