Subsets (Power Set)
Return all subsets (the power set) of an array of distinct integers — 2ⁿ of them.
Open on LeetCode ↗Intuition
Every subset is a chain of n independent yes/no decisions: include this element or not. Backtracking walks that decision tree — take the element, recurse, un-take it, recurse — and every leaf is one subset. Equivalently, each n-bit number 0..2ⁿ−1 is a subset: bit i set means take nums[i].
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
Include / exclude recursion
dfs(i, path): at each index, branch on taking nums[i] or skipping it; at i == n, snapshot path. 2ⁿ leaves = 2ⁿ subsets.
Snapshot every node instead
The common variant records path on entry and only branches on which later element to add next — same output, no explicit base case.
Bitmask alternative
for mask in range(2**n): build the subset from set bits. Iterative, no recursion, same O(n·2ⁿ).
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.