Generate All Subsets (Power Set): Three Approaches Explained

Generating all subsets (the power set) is a fundamental combinatorics problem that tests backtracking, bit manipulation, and your understanding of exponential state spaces. It’s asked at Google, Facebook, and Amazon and is the base for combination sum, permutations, and partitioning problems.

Problem

Given an array of distinct integers, return all possible subsets (the power set). An array of n elements has exactly 2^n subsets.

Backtracking Solution

def subsets(nums: list[int]) -> list[list[int]]:
    """
    Backtracking: at each index, choose to include or exclude the element.
    Build subset incrementally; add a copy to results at each call.
    Time: O(n * 2^n), Space: O(n) for recursion stack
    """
    result = []

    def backtrack(start, current):
        result.append(current[:])  # Add copy of current subset

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()  # Backtrack

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Iterative / Cascading Solution

Start with [[]]. For each number, duplicate all existing subsets and add the number to each duplicate:

def subsets_iterative(nums: list[int]) -> list[list[int]]:
    """
    Cascade: start with [[]], for each num add it to all existing subsets.
    Time: O(n * 2^n), Space: O(2^n) for the result
    """
    result = [[]]

    for num in nums:
        # Add num to every existing subset to create new subsets
        new_subsets = [subset + [num] for subset in result]
        result.extend(new_subsets)

    return result

Bit Manipulation Solution

Each subset corresponds to a bitmask from 0 to 2^n – 1:

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    """
    Each number from 0 to 2^n - 1 represents a subset.
    Bit i set = include nums[i] in the subset.
    Time: O(n * 2^n), Space: O(2^n)
    """
    n = len(nums)
    result = []

    for mask in range(1 << n):  # 0 to 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)

    return result

# Example: nums = [1, 2, 3]
# mask=0 (000): []
# mask=1 (001): [1]
# mask=2 (010): [2]
# mask=3 (011): [1, 2]
# ...
# mask=7 (111): [1, 2, 3]

Subsets With Duplicates (LeetCode 90)

When the input has duplicates, sort first and skip duplicate elements at the same recursion level:

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """
    LeetCode 90: return all unique subsets when nums may have duplicates.
    Sort first, then skip duplicate elements at the same recursion depth.
    """
    nums.sort()
    result = []

    def backtrack(start, current):
        result.append(current[:])

        for i in range(start, len(nums)):
            # Skip duplicate at same level (not the first occurrence)
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

print(subsets_with_dup([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]]  — no duplicate [1,2] entries

The Subset Pattern Family

Subsets is the base template for:

Problem	Variation
Combinations (LeetCode 77)	Only subsets of exactly size k
Combination Sum (LeetCode 39)	Subsets that sum to target; elements reusable
Combination Sum II (LeetCode 40)	Sum to target; duplicates, each used once
Permutations (LeetCode 46)	Ordered subsets using all elements
Letter Case Permutation (LeetCode 784)	Flip case of each letter — 2^letters subsets

Complexity Analysis

Time: O(n × 2^n) — 2^n subsets, each taking O(n) to copy
Space: O(n × 2^n) for the result; O(n) for the recursion stack

The 2^n factor is unavoidable — you’re explicitly generating an exponential number of subsets.