Subsets (bitmask enumeration) (LeetCode 78)

The problem

You get an array of distinct integers. Return every possible subset (the power set), in any order, with no duplicate subsets. The empty set and the full array both count.

Input:  [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Three items give 2³ = 8 subsets.

How to think about it

Start with the count. For each item you make one yes/no choice: take it or leave it. With n items that is 2ⁿ combinations, and each subset can have up to n items, so any solution is at least O(n·2ⁿ) just to write the output. The question is how to enumerate the choices cleanly.

The usual way is backtracking, as in Subsets: recurse, and at each index either include the item or not. That works well, but needs recursion and careful copying of the current list.

The key insight: a string of n yes/no choices is an n-bit number. Let bit i mean “item i is in the subset”. Then every integer from 0 to 2ⁿ − 1 is exactly one subset, and every subset is exactly one integer. Counting from 0 to 2ⁿ − 1 visits every subset once, with no recursion. To decode a mask, test each bit with mask & (1 << i).

Which pattern is this? Bit manipulation, bitmask enumeration. The tell is “all subsets” with small n (up to about 20), and it is the same encoding used later for bitmask DP, where a mask stands for “which items have been used”.

Approach

1. Let n = len(nums).
2. For every mask from 0 to 2ⁿ − 1 (range(1 << n)):
3. Build the subset of nums[i] for each i whose bit is set in mask.
4. Append it to the result. Return the result.

Solution

def subsets(nums):
    n = len(nums); res = []
    for mask in range(1 << n):                                   # 0 .. 2^n - 1
        res.append([nums[i] for i in range(n) if mask & (1 << i)])  # bit i set -> take nums[i]
    return res
# subsets([1,2,3]) -> 8 subsets, including [], [1], [1,2], [1,2,3], ...

Dry run

On [1, 2, 3], bit 0 is item 1, bit 1 is item 2, bit 2 is item 3 (masks are written high bit first):

Eight masks, eight subsets: exactly the output above.

Complexity

• Time: O(n·2ⁿ). There are 2ⁿ masks, and decoding each one checks n bits.
• Space: O(n·2ⁿ) for the output. Apart from that, only the current mask and list.

Edge cases and pitfalls

• Empty input gives [[]]: range(1 << 0) has one mask, 0.
• Duplicates in the input produce duplicate subsets. That is Subsets II, which needs sorting and skipping.
• Large n. 2ⁿ explodes fast; for n around 20 that is already a million subsets. The constraints here keep n at 10 or less.
• Operator precedence. Write mask & (1 << i) with brackets. In some languages & binds more loosely than comparisons, which causes silent bugs.

Related problems

• Subsets (LeetCode 78): the same problem solved with backtracking.
• Subsets II (LeetCode 90): the version with duplicates.
• Partition to K Equal Sum Subsets (LeetCode 698): bitmasks as “which items are used” state.