#78 Subsets
frequently reported atBloombergAmazonMetaMicrosoftGoogleUber
the problem
In plain words
Given an array of distinct integers, return every possible subset (the power set). The answer may be in any order and must not contain duplicate subsets.
in nums = [1,2,3]
out [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
in nums = [0]
out [[],[0]]
- 1 ≤ nums.length ≤ 10
- -10 ≤ nums[i] ≤ 10
- All values are distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBacktracking: subsetsBitmask as a set
Every element is either in or out — 2ⁿ subsets. In the backtracking tree, every node (not just leaves) is a subset, so record on arrival.
solutions
From brute force to optimal
Start with [[]]. For each number, copy every existing subset and add the number to the copy.
- result = [[]].
- For each x: for each subset that existed before x, add subset + [x].
- After n numbers there are 2ⁿ subsets.
2ⁿ subsets are created, each copied in up to O(n).
Only the output — no recursion.
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); // start with the empty set for (int x : nums) { int size = result.size(); // freeze: only extend what existed before x for (int i = 0; i < size; i++) { List<Integer> withX = new ArrayList<>(result.get(i)); withX.add(x); result.add(withX); } } return result; }}The numbers 0 … 2ⁿ−1 in binary are exactly the in/out patterns: bit i on means nums[i] is in.
- For mask in 0 .. (1 << n) − 1:
- collect nums[i] for every set bit i.
2ⁿ masks × n bit tests.
One subset under construction (excluding output).
class Solution { public List<List<Integer>> subsets(int[] nums) { int n = nums.length; List<List<Integer>> result = new ArrayList<>(); 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]); // bit i on: take nums[i] } result.add(subset); } return result; }}Bitmask dry run
Record the current path, then for each index i ≥ start: choose nums[i], recurse with i + 1, un-choose.
- Record a copy of path.
- Loop i from start to n − 1.
- path.add(nums[i]); recurse(i + 1); path.remove(last).
2ⁿ nodes, each recorded with an O(n) copy — optimal, since the output has that size.
Recursion depth and path length are at most n (excluding output).
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) { result.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, result); path.remove(path.size() - 1); } }}Dry run
in the room
How to say it in the interview
talk track
- "Each element is in or out, so there are 2ⁿ subsets — I can't beat O(n·2ⁿ) because that's the output size."
- Explain the tree: node = current subset, children = add one later element. Record at every node.
- Offer the bitmask version as a one-liner alternative; it shows you see the binary structure.
traps
- Recording only at leaves (gives just the full set).
- Adding
pathwithout copying it.
what they ask next
Follow-ups
What if nums has duplicates?
That's LC 90 Subsets II: sort, then skip nums[i] == nums[i-1] when i > start.
Only subsets of size k?
That's LC 77 Combinations: record only when path.size() == k, and prune when too few elements remain.
Iterate only the submasks of a mask?
for (int s = mask; s > 0; s = (s - 1) & mask) visits every non-empty submask. Over all masks the total work is O(3ⁿ).
before you submit
Edge cases to test
- One number → [[], [x]]: the empty subset counts too.
- Negative numbers change nothing: only positions matter, not values.
- 10 numbers → 2¹⁰ = 1,024 subsets, the most the constraints allow.
practise next
Similar problems
- #90Subsets IIMediumin Backtracking
- #77CombinationsMediumin Backtracking
- #416Partition Equal Subset SumMediumin Dynamic Programming