Subsets
Problem Statement
Given an integer array nums of unique elements, return all possible subsets of nums. The solution set must not contain duplicate subsets, and the order of subsets in the output may be arbitrary.
Input
An integer array nums containing unique values.
Output
A list of lists containing every subset of nums exactly once.
Constraints
- •
1 <= nums.length <= 10 - •
-10 <= nums[i] <= 10 - •
All values in nums are unique
Examples
Example 1
nums = [1,2,3]
[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]Example 2
nums = [0]
[[],[0]]Learning Objectives
- Recognise **enumerate all subsets** as the subset backtracking pattern.
- Use a **start** pointer so every recursive choice only considers later indices.
- Record the current path at every recursion node because every partial choice is a valid subset.
- Explain the equivalent binary framing where each index is either taken or skipped.
Intuition
Pattern Recognition
The phrase all possible subsets is the giveaway. We are not optimizing one answer; we must enumerate every valid configuration. For a subset, there is no fixed final length. The empty path is valid, a one-element path is valid, and so is any longer path that preserves the original index order.
The subset pattern keeps two pieces of state: start, the first index still available, and path, the elements chosen so far. At each recursion frame, record a copy of path immediately, then try choosing each candidate from start onward. Choosing nums[i] moves the next frame to i + 1, which means the same element cannot be reused and earlier elements cannot be reordered back into the subset.
You can also view the same search as a binary take-or-skip decision at every index: take nums[i] and move forward, or skip it and move forward. The start-index loop is the compact interview version of that decision tree, and every node in the tree represents one answer.
Common mistakes
- ×Recording a subset only at the leaf, which misses shorter subsets like **[]** and **[1]** in the loop-style DFS.
- ×Recursing with the same index after choosing, which allows reusing an element and turns the problem into a combination-sum variant.
- ×Adding **path** directly to the result instead of adding a copy, causing every stored subset to mutate later.
- ×Starting the loop from **0** in every frame, which generates duplicate orders such as **[1,2]** and **[2,1]**.
Algorithm Explanation
State
Each recursion frame carries start and path. start is the first index that may still be chosen, and path is the subset built by previous choices. The result list stores copies of paths, not references to the mutable working list.
Recursion tree
For nums = [1,2,3], the root has path = [] and records the empty subset immediately. From the root, choose 1 to enter the branch [1], then choose 2 for [1,2], then choose 3 for [1,2,3]. After unchoosing 3 and 2, the [1] branch can choose 3 directly, creating [1,3]. Back at the root, choosing 2 creates [2], then [2,3]. Finally, choosing 3 from the root creates [3]. Notice that every node, not just every leaf, is an output subset.
Pruning
No value-based pruning is needed because all values are unique. The start pointer is the structural pruning: it prevents reusing an index and prevents permuted duplicates such as [2,1] after [1,2] has already represented that combination of elements.
Algorithm
- Create an empty result list and an empty path.
- Enter DFS with start = 0.
- Add a copy of path to the result at the start of every frame.
- For each index from start to the end, choose nums[index] by appending it to path.
- Explore the next frame with start = index + 1.
- Unchoose by removing the last value so the next sibling branch starts clean.
- Return the result after DFS finishes.
Solutions
Solution: Start-index subset DFS
Use the canonical subset DFS template: record the current path, then append one later element at a time and recurse beyond that element. The start pointer keeps each subset in index order, so every unique selection appears exactly once.
Step-by-step
- Create result and call the helper with start = 0 and an empty path.
- In every helper call, add a new copy of path to result.
- Loop index from start through the end of nums.
- Add nums[index] to path to choose it for the current subset.
- Recurse with index + 1 so later choices can only use later numbers.
- Remove the last value from path before trying the next index.
O(2^n * n)
O(n)
There are 2^n subsets and copying a path can cost up to n. Auxiliary recursion space is O(n); output storage is O(2^n * n).
Java implementation
Dry Run
Sample input
nums = [1,2,3]. Track the current recursion depth, the choice being made, and when a path is copied into the answer.
| depth | choice | path | action | result added |
|---|---|---|---|---|
| 0 | enter start 0 | [] | record current path | [] |
| 0 | choose 1 | [1] | explore from index 1 | pending |
| 1 | enter start 1 | [1] | record current path | [1] |
| 1 | choose 2 | [1,2] | explore from index 2 | pending |
| 2 | enter start 2 | [1,2] | record current path | [1,2] |
| 2 | choose 3 | [1,2,3] | explore from index 3 | pending |
| 3 | enter start 3 | [1,2,3] | record current path | [1,2,3] |
| 2 | unchoose 3 | [1,2] | return to sibling choices | none |
| 1 | unchoose 2, choose 3 | [1,3] | explore from index 3 | pending |
| 2 | enter start 3 | [1,3] | record current path | [1,3] |
| 0 | unchoose 1, choose 2 | [2] | explore from index 2 | pending |
| 1 | enter start 2 | [2] | record current path | [2] |
| 1 | choose 3 | [2,3] | explore from index 3 | pending |
| 2 | enter start 3 | [2,3] | record current path | [2,3] |
| 0 | choose 3 | [3] | explore from index 3 | pending |
| 1 | enter start 3 | [3] | record current path | [3] |
The final result contains [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], and [3]. The order can vary, but every subset is produced once because the start pointer only moves forward.
Interview Tips
Say early that every recursion node is an answer. That sentence prevents the most common leaf-only mistake. Then name the two equivalent framings: a binary take-or-skip tree over indices, or the start-index DFS loop that chooses the next included element. Interviewers usually prefer the start-index version because it naturally extends to duplicates and combinations.
Likely follow-ups
- How would the solution change if **nums** could contain duplicate values?
- How would you generate only subsets of size exactly **k**?
- How would you stream subsets one at a time instead of storing all of them?
- How would the recursion tree differ in the explicit take-or-skip implementation?
Similar Problems
Key Takeaways
- Subsets are an enumeration problem, not an optimization problem.
- Record **path** at every node because every partial selection is valid.
- A forward-moving **start** pointer prevents reuse and permutation duplicates.
- Always copy the mutable path before storing it in the result.