Subsets (Power Set)
Return all subsets (the power set) of an array of distinct integers — 2ⁿ of them.
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
Intuition
The subsets problem asks for the power set — every subset of a list of distinct integers, all 2ⁿ of them. Since the output itself has 2ⁿ entries, no approach can be faster than exponential. The task is to enumerate them without duplicates and without omissions.
The clearest framing is a chain of independent decisions. For each element you choose to include it or leave it out, and different choices give different subsets. With n elements that is n binary decisions, and the 2ⁿ leaves of that decision tree are exactly the 2ⁿ subsets — no two the same, none missing.
That gives the backtracking form: at index i, recurse once having added nums[i] to the current path, and once without it. At i == n the path is a complete subset, so record a copy of it.
There is a second, equally common formulation worth knowing, where a subset is recorded at every node of the recursion rather than only at leaves, and each call chooses which later element to add next. It produces the same 2ⁿ subsets and needs no explicit base case.
And there is a neat iterative alternative. Every subset corresponds to an n-bit number: bit i set means take nums[i]. So looping mask from 0 to 2ⁿ − 1 and reading its bits enumerates the power set with no recursion at all — the same complexity, expressed as counting.
One detail matters in every version: append a copy of the path, not the path itself, or later mutations corrupt results already stored.
The power set as a prefix tree: every node in the recursion is a subset, so you record on entry rather than only at the leaves. The j + 1 in the recursive call is what keeps combinations from becoming permutations. Recognise the family — subsets, subsets II, combinations — by whether elements are chosen without regard to order.
Approach
Before reading on: price up what plain recursion costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n · 2ⁿ) time and O(n) space.
Model each element as an in-or-out choice
At index i, branch twice: once including nums[i] and once excluding it. Each distinct combination of choices yields one distinct subset, so this enumerates all 2ⁿ without repeats.
Record a copy at the base case
When i reaches the length, every element has been decided and the current path is a complete subset. Append a copy — appending the live list stores a reference that subsequent backtracking will mutate, corrupting earlier results.
Undo the choice after recursing
After the include branch returns, pop the element before taking the exclude branch. This is what keeps the path accurate for the sibling subtree, and forgetting it produces subsets containing elements from unrelated branches.
Know the record-at-every-node variant
An alternative appends the current path on entry and loops over which later element to add next. It emits the same 2ⁿ subsets with no explicit base case, and is the form most often seen in solutions — worth recognising when reading other people's code.
Use a bitmask for the iterative version
For mask from 0 to 2ⁿ − 1, include nums[i] whenever bit i of mask is set. This maps subsets onto integers exactly, needs no recursion, and is the easiest version to reason about when recursion depth is a concern.
Cost is set by the output
There are 2ⁿ subsets averaging n/2 elements, so producing them is O(n · 2ⁿ) time — dominated by copying, not by deciding. Space is the same for the output plus O(n) for the recursion stack.
Solution & live demo
Common pitfalls
Only recording at the leaves
def dfs(i):
if i == len(nums):
res.append(path[:])
returndef dfs(i):
res.append(path[:])
for j in range(i, len(nums)):
...Every partial path is itself a valid subset, so the answer lives at every node of the tree, not just the bottom. Recording only at leaves returns a fraction of the 2^n subsets.
Recursing with j instead of j + 1
dfs(j)
dfs(j + 1)
Passing j lets the same element be chosen again, generating multisets like [1, 1] from a single 1. Advancing past it enforces that each element is considered exactly once per path.
Appending path by reference
res.append(path)
res.append(path[:])
path is mutated throughout the search, so every stored reference ends up showing the same final state — an empty list. The snapshot has to be a copy.
Edge cases
Power set is [[]] — one empty subset.
The all-skip and all-take branches produce them.
Append path[:], not path — the list mutates during backtracking.