Subsets

Problem Statement

Given an array of distinct integers, return all possible subsets (the power set). The answer may be in any order, and must not contain duplicates.

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

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

Intuition

There are 2³ = 8 subsets of a 3-element list, and that 2ⁿ is the clue.

Why exactly 2ⁿ? Because building a subset means walking the list once and making one yes/no decision per element: is this element in, or out? Three elements, two options each, 2 × 2 × 2 = 8.

The decision tree

                       []
                 /            \
            take 1            skip 1
            /    \            /    \
       take 2   skip 2   take 2   skip 2
        /  \     /  \     /  \      /  \
      t3  s3   t3  s3   t3  s3    t3  s3
       |   |    |   |    |   |     |   |
   [1,2,3][1,2][1,3][1] [2,3][2]  [3]  []

Eight leaves, eight subsets. Backtracking walks this tree depth-first.

The start index, and why it exists

Without care you would produce [1, 2] and [2, 1] — the same subset twice, since order does not matter in a set.

The fix is a start index: when choosing the next element, only look at positions after the one just taken. That forces every subset into increasing order, so each one can be built exactly one way.

With start:     [1,2]  produced once
Without start:  [1,2]  and  [2,1]  — duplicates

Approach

Watch it run

Solution

def subsets(nums: list[int]) -> list[list[int]]:
    """Return every subset of a list of distinct integers."""
    results: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        # Every path is a valid subset — record a COPY, not the live array.
        results.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])      # choose
            backtrack(i + 1)          # explore, never looking back
            path.pop()                # undo

    backtrack(0)
    return results


def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    """Alternative: the bits of 0..2^n - 1 spell out the include/exclude choices."""
    n = len(nums)
    results: list[list[int]] = []

    for mask in range(1 << n):  # 1 << n is 2^n
        # Bit i set means "include nums[i]".
        results.append([nums[i] for i in range(n) if mask & (1 << i)])

    return results

Complexity Analysis

• Time — there are 2ⁿ subsets, and copying each one into the results costs up to O(n). The recursion itself does O(2ⁿ) work; the copying is what adds the factor of n.
• Space — excluding the output, only the path array and the recursion stack, both at most n deep. Including the output, it is O(n · 2ⁿ) because that is simply how big the answer is.

Edge Cases

Related Problems

• Permutations — order matters, so every element stays available
• Combination Sum — the same start index, plus reuse and pruning
• Backtracking — the choose / explore / undo template