Subsets — Power Set Enumeration With Bitmask Iteration

Problem Statement#

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Example 1:

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

Example 2:

Input:  nums = [0]
Output: [[], [0]]

Example 3:

Input:  nums = [1, 2]
Output: [[], [1], [2], [1, 2]]

Why This Problem Matters#

Subsets is a foundational interview problem because the power set appears everywhere: feature flag combinations, exhaustive testing of small input domains, brute-forcing matchings, and the inner loop of bitmask DP for problems like Traveling Salesman or Partition Equal Sum K Subsets. Whether you choose backtracking or bitmask iteration, this problem teaches you to enumerate all 2^n subsets cleanly.

The bitmask approach is especially loved by FAANG interviewers because it shows that you can map a structural concept (subset inclusion) onto a numeric primitive (bit position), unlocking constant-time set operations like union, intersection, and complement. Once you internalize that subsets and bitmasks are isomorphic, problems like Number of Valid Words for Each Puzzle (LC 1178) and Maximum Product of Word Lengths (LC 318) suddenly become tractable.

The Core Insight#

For an array of n elements, there are exactly 2^n subsets. Each subset corresponds bijectively to an n-bit binary number where bit i is set if and only if element i is included.

For nums = [a, b, c] (n = 3):

Iterating mask from 0 to 2^n - 1 produces every subset exactly once with no duplicates and no recursion stack:

for mask in 0..(1 << n):
    subset = [nums[i] for i in 0..n if mask & (1 << i)]
    output.append(subset)

This is O(2^n * n) — optimal because the output itself has size Theta(2^n * n).

Visual Dry Run#

Input: nums = [1, 2, 3]

Iterate masks 0 through 7:

Eight distinct subsets — exactly the power set.

Solution (Optimal)#

Python#

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        # Each mask in [0, 2^n) is the binary signature of one subset
        n = len(nums)
        result = []
        for mask in range(1 << n):
            # Pick element i if bit i is set in mask
            subset = [nums[i] for i in range(n) if mask & (1 << i)]
            result.append(subset)
        return result
 
class SolutionBacktracking:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        # Equivalent recursive enumeration — useful when n is large
        result = []
 
        def backtrack(start: int, current: list[int]) -> None:
            result.append(list(current))   # snapshot every prefix as a subset
            for j in range(start, len(nums)):
                current.append(nums[j])
                backtrack(j + 1, current)
                current.pop()              # undo the choice (classic backtracking)
 
        backtrack(0, [])
        return result

JavaScript#

var subsets = function(nums) {
    // Bitmask enumeration: each mask 0..2^n-1 is one subset
    const n = nums.length;
    const result = [];
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let i = 0; i < n; i++) {
            // include nums[i] iff bit i of mask is set
            if (mask & (1 << i)) subset.push(nums[i]);
        }
        result.push(subset);
    }
    return result;
};

Complexity: Time O(2^n * n), Space O(2^n * n) for the output (the bitmask iteration adds no extra memory beyond it).

Common Mistakes#

1. Iterating up to 1 << n exclusive vs inclusive. The valid range is [0, 1 << n) — that is 2^n total masks. Including 1 << n itself would generate one extra invalid subset.

2. Indexing the bit incorrectly. mask & (1 << i) tests bit i. Using mask & i or mask >> i without & 1 returns wrong values.

3. Mutating current instead of cloning in backtracking. When using the recursive approach, you must result.append(list(current)) (Python) or push a copy in JS. Pushing the same reference causes every output entry to mutate together.

4. Overflow at n = 32 or beyond. In JavaScript, 1 << 31 becomes negative due to 32-bit signed semantics. For larger n, use BigInt or Python's arbitrary-precision integers.

5. Sorting output unnecessarily. The problem allows any order. Sorting wastes time without improving correctness.

Interview Tips#

• State up front: "There are 2^n subsets, each one a bitmask." This frames the entire solution succinctly.
• Mention both bitmask and backtracking. The bitmask form is iterative and cache-friendly; the backtracking form generalizes more naturally to constraints like "subsets of size k" or "no two adjacent elements."
• Discuss complexity carefully — the lower bound is Theta(2^n * n) because the output itself has that size, so neither approach can be asymptotically better.
• If the interviewer extends to "subsets with sum equal to S", pivot to bitmask DP or pruned backtracking; this question is the building block.

Follow-up Questions#

Q: How would you generate subsets in lexicographic order of the elements? Iterate masks but use bit i to mean "include the i-th element of a sorted nums." Alternatively, sort the array first and use backtracking; recursion naturally yields lex order.

Q: What if duplicates are allowed (LC 90 Subsets II)? Sort the array and skip duplicate masks, or use backtracking with a "skip if nums[i] == nums[i-1] and i is the first decision after a recursive return" rule.

Q: How would you generate only subsets of size k? Iterate masks where popcount(mask) == k, or use a Gosper's hack to iterate over masks with a fixed popcount in O(C(n, k)) time.

Q: How does this map to a hash set or bitset data structure? A bitmask is literally a bitset over n elements. Union is mask1 | mask2, intersection is mask1 & mask2, complement is ~mask & ((1 << n) - 1). These operations are O(1) for n up to word size.

Key Takeaways#

• The power set has 2^n subsets; each maps bijectively to an n-bit mask where bit i means "include element i".
• Iterate mask from 0 to 2^n - 1 and read off the included elements via mask & (1 << i).
• Total complexity is O(2^n * n) — optimal, since the output has that size.
• Bitmask iteration is iterative, allocation-free per mask, and easy to parallelize compared to recursive backtracking.
• The same idea generalizes to bitmask DP, traveling salesman, masked combinations, and bitset-based set operations.
• Watch for 32-bit signed overflow in JavaScript when n approaches 31; use BigInt if needed.