Subsets with a Bitmask

Every subset of an n-item list is a yes/no decision for each item — which is exactly what n bits are. So the 2ⁿ subsets are simply the numbers 0 to 2ⁿ − 1. This lesson uses the classic Subsets problem to teach the most useful idea in bit manipulation beyond XOR: an integer as a small set. The same idea powers bitmask dynamic programming and many "n ≤ 20" problems.

The problem

Given a list of distinct integers, return all of its subsets (the power set). The order of the subsets, and of items inside each subset, does not matter. Do not return duplicates.

Example 1. [7, 8, 9] → 8 subsets: [], [7], [8], [7, 8], [9], [7, 9], [8, 9], [7, 8, 9].

Example 2. [0] → [[], [0]].

Constraints. 1 ≤ n ≤ 10, values distinct.

Clarifying questions

• Are values distinct? Yes. (With duplicates, see the follow-ups.)
• Is the empty subset included? Yes.
• Any required order? No.
• How large can n be? 10 here. The output alone has n × 2ⁿ⁻¹ items, so n can never be large — at n = 20 that is over 10 million numbers.

Approach 1: the simple way — backtracking

For each item, make two choices: leave it out, or take it. Recurse to the next item. When every item has been decided, record the current choice.

1def subsets_backtrack(nums: list[int]) -> list[list[int]]:2    """For each item, branch on 'leave it out' and 'take it'."""3    result: list[list[int]] = []4    current: list[int] = []56    def build(i: int) -> None:7        if i == len(nums):8            result.append(current.copy())9            return10        build(i + 1)                 # leave nums[i] out11        current.append(nums[i])12        build(i + 1)                 # take nums[i]13        current.pop()1415    build(0)16    return result

This is the standard solution from the backtracking section. It is O(n × 2ⁿ) time, which is the best possible because the output itself has that size. There is nothing "too slow" here. What the bitmask adds is a different way to name each subset — as a single integer — and that name is what later problems need.

The key insight

Write the decisions for [7, 8, 9] as bits: bit 0 for 7, bit 1 for 8, bit 2 for 9. A 1 means "take it". Then each subset is a 3-bit number, and each 3-bit number is a subset:

Counting from 0 to 2ⁿ − 1 visits every combination of n bits exactly once — that is what counting in binary is. So a plain for loop replaces the recursion, and each subset gets a compact, hashable ID: its mask.

Approach 2: count through the masks

1def subsets(nums: list[int]) -> list[list[int]]:2    """Each mask from 0 to 2^n - 1 is one subset: bit i set means take nums[i]."""3    n = len(nums)4    result = []5    for mask in range(1 << n):                     # 0 .. 2^n - 16        result.append([nums[i] for i in range(n) if (mask >> i) & 1])7    return result

Step by step:

1. 1 << n is 2ⁿ, the number of subsets.
2. For each mask, test each bit i with (mask >> i) & 1.
3. Collect the items whose bits are on.

Dry run on [7, 8, 9] for three of the eight masks:

The full output, in mask order, is [[], [7], [8], [7, 8], [9], [7, 9], [8, 9], [7, 8, 9]].

Complexity. O(n × 2ⁿ) time: 2ⁿ masks, and n bit tests per mask. O(n × 2ⁿ) space for the output, and no recursion stack.

Approach 3: build each subset from a smaller one

Approach 2 tests all n bits of every mask, even the zeros. There is a neater way. Every non-zero mask is a smaller mask plus one extra bit — its lowest set bit. The smaller mask's subset is already built, so copy it and append one item:

1def subsets_reuse(nums: list[int]) -> list[list[int]]:2    """subset[mask] = subset[mask without its lowest bit] + that bit's item."""3    result: list[list[int]] = [[]]4    for mask in range(1, 1 << len(nums)):5        low = mask & -mask                          # isolate the lowest set bit6        result.append(result[mask ^ low] + [nums[low.bit_length() - 1]])7    return result

For mask 6 (110): the lowest bit is 010, the smaller mask is 100 = 4, whose subset is [9], and bit 1 is item 8, so mask 6 is [9, 8]. It is the Counting Bits idea again: reuse a smaller answer.

Honest numbers. For n = 20 (about a million subsets), measured in Python: backtracking took 0.48 seconds, Approach 3 took 0.64 seconds, and Approach 2 took 1.41 seconds. The bitmask is not faster in Python for plain generation. Its value is elsewhere: no recursion, and every subset has an integer name you can store, compare and index with.

That name is what bitmask problems need. "Do these two words share a letter?" becomes mask_a & mask_b == 0, one instruction. A dynamic programming state like "which cities have I visited?" becomes an index into a list of size 2ⁿ.

Edge cases

• One item. Masks 0 and 1: [] and [x].
• The empty subset. Mask 0 has no bits on and yields []. It is part of the answer.
• Large n. 2ⁿ grows fast: n = 20 is about 10⁶ masks, fine; n = 30 is 10⁹, not fine. When constraints say "n ≤ 20", that is an invitation to enumerate masks.

Follow-ups

• "The list may contain duplicates; return unique subsets." Masks would produce the same subset several times. Sort the list and use backtracking that skips equal neighbours at the same depth — pruning is something a flat mask loop cannot do.
• "Enumerate the subsets of a given mask." The loop sub = (sub - 1) & mask, starting from sub = mask and stopping after 0, visits every submask. For 1011 it visits 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000. Doing this for every mask costs 3ⁿ in total, the basis of many bitmask DP solutions.
• "Maximum product of lengths of two words that share no letter." Turn each word into a 26-bit mask of its letters. Two words share no letter exactly when mask_a & mask_b == 0. Checking a pair becomes one AND instead of comparing strings.