#78
Subsets
Medium Backtracking (pick / not pick)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return every possible subset of an array of distinct integers.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: list every subset.
Why this works: each node of the recursion is a subset. From a start index, try adding each later element, recurse, then remove it.
Example: [1, 2, 3]
[] → [1] → [1,2] → [1,2,3]back → [1,3]back → [2] → [2,3] → [3]8 subsets
✦Hints open one at a time
For each element decide: include it or not.
Or: at each step, the current list is itself a subset — record it, then try adding each later element.
↗Approach
Backtracking: record a copy of the current path, then for i from start to n−1 add nums[i], recurse with start = i + 1, and remove it.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // every node is a subset
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
path.remove(path.size() - 1); // undo the choice
}
}
}!Common mistake
Adding the path itself instead of new ArrayList<>(path) — every stored subset ends up as the same empty list.
Complexity
- Time: O(n · 2^n).
- Space: O(n) recursion besides the output.
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon