Generate all subsets of a set — the power set — using backtracking.
At each step of a recursive walk through the input, you make a binary choice: include the current element or skip it. Recording the current path at every node of the recursion tree (not just the leaves) collects all 2^n subsets. A `start` index prevents duplicates by ensuring elements are only considered left-to-right.
How to think about it
When a problem asks for every selection, arrangement, or partition and the answer count is exponential, the interviewer is testing one skill: can you frame it as a decision tree and walk it with backtracking? Subsets is the gentlest version of that test, because there is no constraint to prune against — every partial path is already a valid subset. So this is where you prove you can build a candidate incrementally, record it, and cleanly undo the last choice before trying the next.
Picture a tree over nums. At each level you decide whether to include the current element, and at every node — not just the leaves — the path you have built so far is one subset of the answer. The recursion captures it in three beats: choose (append nums[i]), explore (recurse from i + 1), un-choose (pop it back off). The start index is the quiet hero — by only ever looking forward from i + 1, it guarantees each element is considered left to right, so [1, 2] is generated but [2, 1] never is. That single rule is what keeps the 2ⁿ subsets unique.
A worked example
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every node is a valid subset -> copy it
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1, path) # explore (start=i+1 -> only look forward)
path.pop() # un-choose (backtrack)
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
print(subsets([0]))
print(subsets([]))
print(len(subsets([1, 2, 3, 4]))) # 2^4 = 16
# The classic bug: append the path itself instead of a copy
def subsets_buggy(nums):
result = []
def backtrack(start, path):
result.append(path) # BUG: stores one shared list object
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print("buggy result:", subsets_buggy([1, 2, 3]))[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
[[], [0]]
[[]]
16
buggy result: [[], [], [], [], [], [], [], []]Two things to read. The correct run lists all eight subsets of [1, 2, 3], and subsets([]) returns [[]] — the empty set still has the empty subset, which is the base case doing its job. Then look at the buggy run: it collected the right number of entries (eight), but every one is []. That is the reference trap made visible — all eight pointed at the same path list, which was emptied back to [] by the time the recursion unwound.