Appearance
4.18.1 — Subsets
LeetCode 78 · Medium · ★ Blind 75
The problem
Return every possible subset of the array. All values are distinct. Any order is fine.
[1,2,3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]n is at most 10, so there are at most 2^{10} = 1024 subsets.
The pattern
Each element is independently in or out. Two choices per element, n elements, so 2^n subsets. That count is the first thing to say — it tells you an exponential answer is expected and correct.
Draw the tree before writing anything:
[]
take 1 / \ skip 1
[1] []
take 2 / \ / \ skip 2
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]Eight leaves, and the leaves are the answers. Every path from the root to a leaf is one decision per element.
Solution 1 — include or exclude
The tree written directly as code.
python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
def backtrack(i: int):
if i == len(nums):
result.append(path[:]) # copy — not path itself
return
path.append(nums[i]) # branch 1: take it
backtrack(i + 1)
path.pop() # undo
backtrack(i + 1) # branch 2: skip it
backtrack(0)
return resultts
function subsets(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
function backtrack(i: number): void {
if (i === nums.length) {
result.push([...path]);
return;
}
path.push(nums[i]);
backtrack(i + 1);
path.pop();
backtrack(i + 1);
}
backtrack(0);
return result;
}path[:] is a copy. Appending path itself stores a reference to the one list that keeps changing, so at the end every entry in result would be the same empty list. This bug produces plausible-looking output that is entirely wrong, and it catches everyone once.
The path.pop() is the undo, restoring the state so the skip branch starts clean.
There is no constraint here — every subset is valid, so nothing is pruned. That is why this is the simplest problem in the chapter: it has three of the four parts and no pruning at all.
Solution 2 — the start-index loop
The same answers from a different tree shape, and this is the version that generalises to every other problem in the chapter.
python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
def backtrack(start: int):
result.append(path[:]) # EVERY node is an answer
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1) # i + 1: never reuse or look back
path.pop()
backtrack(0)
return resultts
function subsets(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
function backtrack(start: number): void {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
backtrack(i + 1);
path.pop();
}
}
backtrack(0);
return result;
}Two things make this version worth learning even though the first one is easier to picture.
Every node is recorded, not just the leaves. A subset is complete at every point in the walk — there is no "unfinished" subset. That is why the result.append sits at the top with no base case. Compare this with permutations, where only full-length paths count.
backtrack(i + 1) means never look back. Starting the loop at start and recursing with i + 1 guarantees each element is considered once and in increasing index order, so [1,2] is generated and [2,1] never is. That is exactly what you want when order does not matter.
Changing that single i + 1 to i allows reuse, and gives you 4.18.2 Combination Sum. One character.
Solution 3 — iterative, no recursion at all
Start with the empty subset. For each element, add a copy of every existing subset with that element appended.
python
def subsets(self, nums):
result = [[]]
for n in nums:
result += [subset + [n] for subset in result]
return result[1,2,3] builds up as:
[[]]
[[], [1]]
[[], [1], [2], [1,2]]
[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]The size doubles with each element, which is the 2^n made visible.
Solution 4 — bitmasks
Each subset corresponds to an n-bit number: bit i set means element i is included.
python
def subsets(self, nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n − 1
result.append([nums[i] for i in range(n) if mask & (1 << i)])
return result1 << n is 2^n. mask & (1 << i) tests bit i.
This is worth knowing because it is the same idea as bitmask dynamic programming, where a subset of up to ~20 items is stored as one integer and used as a DP state (4.29). Seeing subsets as integers here makes that technique much less mysterious later.
Complexity
O(2^n \times n) time. There are 2^n subsets and copying each costs up to O(n).
O(n) space for the recursion and the path, not counting the output.
You cannot do better, because the output itself has 2^n entries. Say this — it reframes the exponential from a failing into a requirement.
Where this goes next
- Subsets II — duplicates in the input. Sort, then skip equal siblings. 4.18.4.
- Combinations (LeetCode 77) — subsets of exactly size k. The same loop with a length check in the base case.
- Combination Sum — the same loop with reuse allowed. 4.18.2.
- Partition Equal Subset Sum — asks whether some subset hits a target. Enumerating all 2^n is too slow, and DP gets there in O(n \times \text{sum}). 4.23. That contrast is worth holding on to: enumerate when you need every answer, use DP when you only need to know whether one exists.
What the interviewer will push on
"How many subsets are there?" 2^n. Say it before you write code.
"Why do you copy the path?" Because it is one shared mutable list.
"Why is every node an answer in the loop version?" A subset is complete at every stage; there is nothing to finish.
"What changes if the array has duplicates?" Sort and skip equal siblings.
"Can you do it without recursion?" The doubling loop, or bitmasks.
One thing to volunteer: draw the tree for [1,2,3] before coding. It takes fifteen seconds and it makes every later problem in this chapter a variation you can see rather than guess.
Next: 4.18.2 Combination Sum — the same loop with one character changed, and the first real pruning.