Subsets
Problem
nums of distinct integers, return its
power set: every possible subset, including the empty set and the full array. No
subset may appear twice; the order of subsets (and within them) does not matter.[1,2,3]Output[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]][0]Output[[],[0]]1 ≤ n ≤ 10 · -10 ≤ nums[i] ≤ 10 · all values distinct
Try it yourself
class Solution {
public List<List<Integer>> subsets(int[] nums) {
}
}
2n subsets. Since the output itself has size
n · 2n, every approach is output-bound — they differ in how
well they extend to constrained / pruned variants.Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.
Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.
Open the Backtracking guide →Approaches
Brute ForceBitmask Enumeration
O(n · 2n)Space O(1) extraCount mask from 0 to 2n-1;
bit i set means nums[i] is in. Every mask is a distinct
subset. Each mask scans all n bits, even for tiny subsets.
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; for (int mask = 0; mask < (1 << n); mask++) { List<Integer> subset = new ArrayList<>(); for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) subset.add(nums[i]); } res.add(subset); } return res; }
Mechanical and loop-only, but can't prune and is capped at n ≤ 30 bits.
BetterIterative Cascading
O(n · 2n)Space O(1) extraStart with [[]]. For each number, copy every subset built so far
and append the number to the copy — the list doubles each step. Subsets
without the number are already present, subsets with it are the new copies.
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); for (int num : nums) { int size = res.size(); // snapshot before adding for (int i = 0; i < size; i++) { List<Integer> next = new ArrayList<>(res.get(i)); next.add(num); res.add(next); } } return res; }
Short and recursion-free; work is spent only on real subsets.
OptimalBacktracking (Start Index)
O(n · 2n)Space O(n) extraEvery node of the recursion tree is a subset: record a copy of
path on entry, then try adding each nums[i] with
i ≥ start, recurse with i+1, and undo. Using
start prevents reordered duplicates like [2,1].
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(0, nums, new ArrayList<>(), res); return res; } private void backtrack(int start, int[] nums, 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(i + 1, nums, path, res); path.remove(path.size() - 1); // undo } }
Uses O(n) stack, but is the template that adapts to Subsets II / Combination Sum.
nums[i] when
i > start && nums[i] == nums[i-1].At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Bitmask Enumeration | O(n · 2n) | O(1) extra |
| Better | Iterative Cascading | O(n · 2n) | O(1) extra |
| Optimal | Backtracking (Start Index) | O(n · 2n) | O(n) extra |
- Iterating over
reswhile appending to it — snapshotsizefirst. - Recursing with
start + 1instead ofi + 1— produces duplicates. - Storing
pathitself rather than a copy.
- Say up front: output is n · 2n, so no approach can beat that.
- Pick backtracking when a follow-up adds constraints (sum target, size k, duplicates).
- Mention the bitmask view: subsets of n items ↔ integers 0 … 2n-1.