Approach Summary
At each index, two choices: include or exclude. Backtrack by adding element, recursing, removing element.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Full Solution & Approach
Subsets are generated by a backtracking recursion that builds the answer incrementally. Define a recursive helper that takes a start index and a working path. At every call, record a copy of the current path into the results — this captures the subset for every prefix of choices. Then loop from start to the end, appending each element, recursing with i + 1, and popping it back off after (the backtrack). Because each element is either included or excluded relative to the recursion tree, every subset appears exactly once. The number of subsets is 2ⁿ, and each subset has length at most n, so the output size bounds the complexity: O(n · 2ⁿ) time and space. The same choose → recurse → unchoose skeleton generates permutations, combinations, and subsets.
There are 2ⁿ subsets, each costing up to O(n) to copy — O(n · 2ⁿ) time. The recursion stores the path (depth ≤ n) plus the 2ⁿ subsets in the output — O(n · 2ⁿ) space.
Solution Code
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));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
path.remove(path.size() - 1);
}
}vector<vector<int>> subsets(const vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
function<void(int)> backtrack = [&](int start) {
res.push_back(path);
for (int i = start; i < (int)nums.size(); i++) {
path.push_back(nums[i]);
backtrack(i + 1);
path.pop_back();
}
};
backtrack(0);
return res;
}def subsets(nums: list[int]) -> list[list[int]]:
res = []
def backtrack(start: int, path: list[int]) -> None:
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resfunction subsets(nums) {
const res = [];
const path = [];
function backtrack(start) {
res.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
backtrack(i + 1);
path.pop();
}
}
backtrack(0);
return res;
}Edge Cases to Watch
- Empty input — returns [[]] (the empty subset)
- Duplicate values — subsets are still distinct by position, e.g. [1] appears twice for [1, 1]
- Single element — [[], [x]]
- Large n — 2ⁿ explodes; problem constraints keep n around 10–20
Master the Backtracking Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Backtracking pattern.
How to Recognize This Pattern
- Generate all subsets/power set
- Include/exclude pattern
Complexity Analysis
Time Complexity
O(n × 2ⁿ)
Space Complexity
O(n)