Subsets is the cleanest backtracking problem there is, and it has one structural difference from every other backtracking problem on the list that is worth spotting out loud: every node of the recursion tree is an answer, not just the leaves. Once you see that, the base case disappears entirely.
The problem
Given an array of distinct integers, return all possible subsets — the power set. The answer may be in any order and must not contain duplicate subsets.
[1,2,3] -> [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] 8 = 2^3
[0] -> [], [0]
[] -> [[]] one subset: the empty one[] returning [[]] rather than [] is the detail to check.
The empty set has exactly one subset — itself — and an answer of "no subsets at all" is a different
claim.
Every node is an answer
In Combination Sum or N-Queens the recursion descends until some condition holds, and only then records something. Here there is no condition: every partial path is a valid subset.
[] <- an answer
/ | \
[1] [2] [3] <- all answers
/ \ |
[1,2] [1,3] [2,3] <- all answers
|
[1,2,3] <- an answerSo the record happens at the top of the function, unconditionally, and the recursion just runs out of candidates on its own. Saying "this is a pre-order traversal where every node is emitted" is exactly the right framing.
The two bugs
Recurse with i + 1, not start + 1. This is the classic
one. start + 1 lets the same element be chosen again at a deeper level and produces
duplicates and repeats; i + 1 says "everything after the element I just took", which is
what keeps each subset's elements in index order and therefore unique.
i + 1 [1,2], [1,3], [2,3] each pair once
start + 1 [1,2], [1,3], [2,2], ... wrongCopy the path when you record it. out.add(path) stores a reference
to the list the recursion is still mutating, so all 2ⁿ entries end up pointing at the
same object — which is empty by the time the function returns. The symptom is a result of the right
length full of identical empty lists, and it looks baffling until you have seen it once.
Java
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
build(nums, 0, new ArrayList<>(), out);
return out;
}
private void build(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
// No base case: every node is an answer, including the empty path.
out.add(new ArrayList<>(path)); // COPY -- path keeps mutating
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
build(nums, i + 1, path, out); // i + 1, not start + 1
path.remove(path.size() - 1); // undo
}
}
}path.remove(path.size() - 1) rather than path.remove(nums[i]) — the
latter resolves to remove(Object) for a boxed Integer and removes the
first equal element, which is a different thing and a genuinely nasty bug when values
repeat. Removing by index is unambiguous.
Python
class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
out: list[list[int]] = []
path: list[int] = []
def build(start: int) -> None:
out.append(path[:]) # a copy, via a slice
for i in range(start, len(nums)):
path.append(nums[i])
build(i + 1)
path.pop()
build(0)
return outpath[:] is the copy. out.append(path) has the identical aliasing bug as
Java, and Python gives you no warning at all.
The bitmask version
There are 2ⁿ subsets and 2ⁿ integers with n bits, and the
correspondence is exact: bit i set means "include nums[i]". No recursion,
no undo, no copying subtlety:
List<List<Integer>> subsetsBits(int[] nums) {
int n = nums.length;
List<List<Integer>> out = new ArrayList<>();
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask >> i & 1) == 1) subset.add(nums[i]);
}
out.add(subset);
}
return out;
}Worth knowing for two reasons beyond brevity. It makes the 2ⁿ count obvious rather
than asserted, and it gives a natural iteration order over subsets — which is the foundation of
subset-mask DP, the technique behind Travelling Salesman on small inputs.
Its limit is n < 31 for an int. That is not a real constraint here,
since 2³¹ subsets is far beyond what could be returned anyway.
There is a third way — start with [[]] and, for each number, append copies of every
existing subset with that number added. It doubles the list n times. Neat, and the
easiest of the three to explain to someone who does not think in recursion.
Complexity
| Time | Space | |
|---|---|---|
| All three approaches | O(n · 2ⁿ) | O(n · 2ⁿ) output |
There are 2ⁿ subsets averaging n/2 elements, so simply writing
the answer is O(n · 2ⁿ). No algorithm can beat that, which is the useful thing to say:
the cost is the output, not the search, and asking to "make it faster" is asking to return less.
Excluding the output, the recursion uses O(n) for the stack and the path.
The pattern
Subsets II (90) allows duplicate inputs, which needs a sort plus the
i > start && nums[i] == nums[i-1] skip — the same de-duplication rule as
Combination Sum II (40) and
Permutations II (47).
Combinations (77) is this stopping at a fixed size, so the record moves back into a
base case. Permutations (46) drops
start altogether, because order matters there and every unused element is a
candidate.
Those four differ only in where the record happens and what the loop is allowed to reach. Lining them up beside each other is a better hour of preparation than solving any one of them twice.
What the interviewer is checking
- That every node is recorded, with no base case.
i + 1in the recursive call.- The defensive copy — and that you can say what breaks without it.
[]returning[[]].- That the empty subset appears in the output.
- That
O(n · 2ⁿ)is the output size, so it cannot be improved. - Bonus: the bitmask correspondence, and
remove(int)versusremove(Object)in Java.