Subsets

Problem

Given an array nums of distinct integers, return all possible subsets — the power set. This includes the empty subset and the full array itself.

The result must not contain duplicate subsets, and you may return the subsets and the elements within each subset in any order.

For an input of size n, there are exactly 2^n subsets (each element is independently either in or out).

Examples

• Input: nums = [1, 2, 3] → Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]] All 2^3 = 8 subsets, from empty to the full set.
• Input: nums = [0] → Output: [[], [0]] A single element gives just the empty set and itself.
• Input: nums = [9, 8] → Output: [[], [9], [8], [9,8]] All 4 subsets of a two-element array.

Constraints

• 1 <= nums.length <= 10.
• -10 <= nums[i] <= 10.
• All integers in nums are distinct.

With n <= 10, the power set has at most 2^10 = 1024 subsets — the output size is inherently exponential.

Think about it first

TL;DR

Backtrack over “include or skip” for each element — O(n · 2^n) time, O(n) recursion depth. Iterative doubling and bitmask enumeration are the classic equivalents.

Approach 1 — Backtracking (include / exclude each element)

The intuition: process elements by index. At index start, first record the current subset, then extend it by choosing each remaining element in turn, recursing and undoing. Recording at every node (not only at leaves) captures subsets of all sizes.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

Walkthrough on nums = [1, 2, 3]:

• backtrack(0) records []. Then:
  • add 1 → record [1]; add 2 → record [1,2]; add 3 → record [1,2,3]; undo 3, undo 2; add 3 → record [1,3]; undo.
  • undo 1; add 2 → record [2]; add 3 → record [2,3]; undo.
  • add 3 → record [3].

Records, in order: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] — all 8 subsets.

Complexity: O(n · 2^n) time (2^n subsets, each up to O(n) to copy), O(n) recursion depth excluding output.

Approach 2 — Iterative doubling (cascading)

The insight: the power set of nums[:k+1] is the power set of nums[:k] plus a copy of every one of those subsets with nums[k] appended. So start from [[]] and, for each new element, double the collection by extending each existing subset.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = [[]]
        for num in nums:
            result += [subset + [num] for subset in result]
        return result

Walkthrough on nums = [1, 2, 3]:

• Start [[]].
• Add 1: [[], [1]].
• Add 2: [[], [1], [2], [1,2]].
• Add 3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]].

Complexity: O(n · 2^n) time and O(n · 2^n) space for the accumulated subsets — no recursion.

Approach 3 — Bitmask enumeration

The insight: there are exactly 2^n subsets, so enumerate integers mask from 0 to 2^n - 1. Bit j of mask decides whether nums[j] is in the subset. This makes the one-to-one correspondence between subsets and binary numbers explicit.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result: List[List[int]] = []
        for mask in range(1 << n):
            subset = [nums[j] for j in range(n) if mask & (1 << j)]
            result.append(subset)
        return result

Walkthrough on nums = [1, 2, 3]: mask = 0 → []; mask = 1 (001) → [1]; mask = 2 (010) → [2]; mask = 3 (011) → [1,2]; … mask = 7 (111) → [1,2,3]. All 8 subsets.

Complexity: O(n · 2^n) time (for each of 2^n masks, inspect n bits), O(1) extra space beyond the output.

Common pitfalls

• Recording only at the leaves. Subsets have every size, so in the backtracking version you must append path[:] at every call, not just when start == len(nums).
• Appending by reference. result.append(path) stores a live alias; snapshot with path[:].
• Reusing earlier elements. Recurse from i + 1, never from start, or you will generate duplicates and permuted repeats.
• Bit-count mismatch. In the bitmask version, loop mask up to 1 << n exclusive; going one too far or using the wrong bit index drops or duplicates subsets.

Pattern takeaway

The power set is the canonical “independent binary choice per element” problem. Recognize that shape and you have three interchangeable tools: recursive include/exclude backtracking, iterative doubling, and direct bitmask enumeration — all O(n · 2^n), differing only in style and whether you want recursion.