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)
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
def subsets(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
Each node below is a subset recorded at one call; a child adds one element whose index is greater than the last, which is why no subset repeats.
flowchart TD
A["[]"] --> B["[1]"]
A --> C["[2]"]
A --> D["[3]"]
B --> E["[1,2]"]
B --> F["[1,3]"]
C --> G["[2,3]"]
E --> H["[1,2,3]"]
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 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. Start from [[]] and, for each new element, double the collection by extending each existing subset.
from typing import List
def subsets(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
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 is the one-to-one correspondence between subsets and binary numbers, made explicit.
from typing import List
def subsets(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. That shape admits three interchangeable tools: recursive include/exclude backtracking, iterative doubling, and direct bitmask enumeration. All run in O(n · 2^n), differing only in style and whether you want recursion.