The problem
Given a list of distinct numbers, return all possible subsets (including the empty one).
Input: [1, 2, 3] Output: [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
Picture it
Picture ordering a pizza. For each topping in turn, you make a yes/no choice: take it or leave it. The picture draws these choices as a decision tree: each level is one topping, each split is take/leave. Every path from the top to the bottom is one complete pizza (one subset). n toppings give 2ⁿ pizzas.
How to recognise it
- The question asks for all subsets, combinations or arrangements, not for one best answer or a count.
- Each item has a small yes/no style choice (take it or leave it), and choices at different items do not interfere.
- The input is tiny (here at most 10 distinct numbers), which hints that the answer set itself is exponential: 2^10 = 1,024 subsets.
- You can describe the answer as a decision tree: one level per item, one branch per choice, and every path from top to bottom is one answer.
- That is backtracking: build a partial answer, recurse to make the next choice, then undo the last choice (un-choose) and try the other one.
Start with brute force
Every subset corresponds to a binary number: bit i says whether nums[i] is in. Count from 0 to 2^n − 1 and build one subset per number.
def subsets_brute(nums):
n = len(nums)
res = []
for mask in range(1 << n):
res.append([nums[i] for i in range(n) if mask >> i & 1])
return res
This is correct and also fast enough here: 2^n masks times n bit tests, so O(n · 2^n) time, and the output itself holds up to n · 2^n numbers. It cannot be beaten much, because the answer alone has 2^n subsets. What it cannot do is prune: if a problem adds a rule such as "sum must equal a target", the mask loop still builds every subset first. The recursive version below is the same count of work, but it is the shape that lets later problems stop early.
From brute force to the idea
- Describe the answer as choices. Walk through the numbers in order. At position
ithere are exactly two options: takenums[i]or leave it. - Keep one shared partial answer.
pickis the list built so far. Taking a number meanspick.append(nums[i]). - Recurse, then undo. After exploring everything that follows the "take" branch,
pick.pop()removes the number again so the "leave" branch starts from the same state. - Stop at the bottom. When
i == len(nums)every number has been decided, sopickis one finished subset. - Copy before saving.
pickkeeps changing, so storepick[:], a copy.
This is the key idea: choose, recurse, un-choose, with a copy taken at each leaf.
The key idea
Backtracking: at each index branch “include” and “exclude”. 2ⁿ subsets.
Python solution
def subsets(nums):
res, pick = [], []
def dfs(i):
if i == len(nums):
res.append(pick[:]) # a finished pizza
return
pick.append(nums[i]) # take topping i
dfs(i + 1)
pick.pop() # leave topping i
dfs(i + 1)
dfs(0)
return resIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Bitmask brute force | O(n · 2^n): 2^n masks, n bit tests each | O(n) beyond the output |
| Take or leave recursion (shown code) | O(n · 2^n): 2^n leaves, each copying up to n numbers | O(n) beyond the output: recursion depth is n + 1 and pick holds at most n numbers |
Edge cases
- Empty list: returns
[[]], one subset (the empty one). - One number (
[5]): returns[[5], []]. - Order of the output: taking comes first, so
[1, 2, 3]returns[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]], matching the example. LeetCode accepts any order. - Maximum size: 10 numbers produce 1,024 subsets, and the recursion is only 11 calls deep.
- Duplicates in the input: the code would return repeated subsets. The problem promises distinct numbers; problem 90 handles duplicates.
- Input is not changed.
Common mistakes
- Appending
pickitself instead ofpick[:]. Every saved entry is the same list, which ends up empty:subsets([1, 2])returns[[], [], [], []]. - Forgetting
pick.pop(). The "leave" branch then still contains the number, sosubsets([1, 2])returns[[1, 2], [1, 2], [1, 2, 2], [1, 2, 2]]. - Starting the recursion at index 1, which skips the first number's choice entirely.
- Looping inside the recursion without a start index, which produces the same subset in several orders.
Return only the subsets that have exactly k numbers (these are called combinations). Describe how you would stop branches that can no longer succeed, then write it if you like.
Compare with our answer
Keep the same take or leave tree and add two rules. Stop when pick already has k numbers (save it). Also stop early when there are not enough numbers left to reach k, since those branches can never produce an answer.
def combinations(nums, k):
res, pick = [], []
def dfs(i):
if len(pick) == k:
res.append(pick[:])
return
if len(pick) + len(nums) - i < k: # too few numbers left
return
pick.append(nums[i])
dfs(i + 1)
pick.pop()
dfs(i + 1)
dfs(0)
return res
combinations([1, 2, 3, 4], 2) returns 6 lists. Time is at most O(n · 2^n) and in practice far less, because many branches stop early; space is O(n) beyond the output.
A strong answer mentions: stopping at length k, the "not enough numbers left" pruning, and why the answer count C(n, k) is smaller than 2^n.
1. A settings screen has 8 independent on/off switches, and a test tool must list every possible combination of them. Which approach fits best?
Listing every combination means exploring a decision tree with two branches per switch: 2^8 = 256 leaves. Greedy and dynamic programming aim at one best answer, and binary search needs a sorted answer space.
2. What is the time complexity of the shown code for n numbers, and why?
There are 2^n leaves, one per subset, and pick[:] copies up to n numbers at each. The tree is a binary choice per level, not a permutation, so n! does not apply.
3. A learner changes res.append(pick[:]) to res.append(pick). What does subsets([1, 2]) return?
pick is one shared list that gets emptied by the final pop calls, so all four saved entries show its final empty state. A copy is needed to freeze each subset as it was at the leaf.
Score 60% or more and the lesson is marked complete.