Subsets
Problem
Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. You may return the solution in any order.
- 1 ≤ nums.length ≤ 10
- −10 ≤ nums[i] ≤ 10
- All elements of nums are unique.
Example
nums = [1,2,3][[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]The algorithm explores the decision tree of including or excluding each element. Starting at index 0 with an empty subset, it chooses to include 1, then recursively explores subsets including 2 and 3, building subsets like [1,2,3]. It backtracks by removing elements and explores alternative branches, such as excluding 1 and including 2 and 3, generating [2,3]. This exhaustive exploration ensures all 2^n subsets are generated without duplicates.
Approach
Straightforward Solution
A brute-force approach enumerates all subsets by iterating over all binary masks from 0 to 2^n - 1, which is feasible but less intuitive and less flexible for extensions.
Core Observation
Each element in nums can either be included or excluded from a subset, leading to a binary decision tree with 2^n leaves representing all subsets.
Path to Optimal
The key insight is to use backtracking to recursively explore the decision space: at each index, choose to include the current element and recurse, then backtrack and choose to exclude it and recurse. This approach naturally generates all subsets without duplicates and allows easy state management.
Optimal Approach
Implement a depth-first search (DFS) that at each step decides whether to include nums[i] in the current subset. When the index reaches the length of nums, append a copy of the current subset to the results. Backtracking by popping the last element after exploring the include branch ensures the state is restored for the exclude branch. This yields all subsets in O(n * 2^n) time and space.
Time
O(n * 2^n)
There are 2^n subsets, and each subset takes O(n) time to copy into the result list. The recursion explores all branches of the binary decision tree.
Space
O(n)
The recursion stack and the temporary subset list use O(n) space, where n is the length of nums. The output list uses O(n * 2^n) space but is not counted as auxiliary space.
Pattern Spotlight
Backtracking (State Restoration)
For problems requiring all combinations or subsets, use a recursive 'choose, explore, un-choose' pattern where each decision point branches on including or excluding the current element, and state is restored after exploring each branch to enable exhaustive search without duplication.
Solution
| 1 | class Solution:
|
| 2 | def subsets(self, nums: list[int]) -> list[list[int]]:
|
| 3 | res = []
|
| 4 | subset = []
|
| 5 |
|
| 6 | def dfs(i):
|
| 7 | if i >= len(nums):
|
| 8 | res.append(subset.copy())
|
| 9 | return
|
| 10 |
|
| 11 | subset.append(nums[i])
|
| 12 | dfs(i + 1)
|
| 13 |
|
| 14 | subset.pop()
|
| 15 | dfs(i + 1)
|
| 16 |
|
| 17 | dfs(0)
|
| 18 | return res |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.List; |
| 3 | |
| 4 | class Solution { |
| 5 | public List<List<Integer>> subsets(int[] nums) { |
| 6 | List<List<Integer>> res = new ArrayList<>(); |
| 7 | List<Integer> subset = new ArrayList<>(); |
| 8 | dfs(nums, 0, subset, res); |
| 9 | return res; |
| 10 | } |
| 11 | |
| 12 | private void dfs(int[] nums, int i, List<Integer> subset, List<List<Integer>> res) { |
| 13 | if (i >= nums.length) { |
| 14 | res.add(new ArrayList<>(subset)); |
| 15 | return; |
| 16 | } |
| 17 | |
| 18 | subset.add(nums[i]); |
| 19 | dfs(nums, i + 1, subset, res); |
| 20 | subset.remove(subset.size() - 1); |
| 21 | dfs(nums, i + 1, subset, res); |
| 22 | } |
| 23 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | vector<vector<int>> subsets(vector<int>& nums) { |
| 8 | vector<vector<int>> res; |
| 9 | vector<int> subset; |
| 10 | dfs(nums, 0, subset, res); |
| 11 | return res; |
| 12 | } |
| 13 | |
| 14 | private: |
| 15 | void dfs(const vector<int>& nums, int i, vector<int>& subset, vector<vector<int>>& res) { |
| 16 | if (i >= (int)nums.size()) { |
| 17 | res.push_back(subset); |
| 18 | return; |
| 19 | } |
| 20 | |
| 21 | subset.push_back(nums[i]); |
| 22 | dfs(nums, i + 1, subset, res); |
| 23 | subset.pop_back(); |
| 24 | dfs(nums, i + 1, subset, res); |
| 25 | } |
| 26 | }; |
| 1 | var subsets = function(nums) { |
| 2 | const res = []; |
| 3 | const subset = []; |
| 4 | |
| 5 | function dfs(i) { |
| 6 | if (i >= nums.length) { |
| 7 | res.push(subset.slice()); |
| 8 | return; |
| 9 | } |
| 10 | |
| 11 | subset.push(nums[i]); |
| 12 | dfs(i + 1); |
| 13 | subset.pop(); |
| 14 | dfs(i + 1); |
| 15 | } |
| 16 | |
| 17 | dfs(0); |
| 18 | return res; |
| 19 | }; |
Step-by-Step Solution
Initialize Result and Temporary Subset Containers
| 3 | res = []
|
| 4 | subset = []
|
Objective
To prepare storage for accumulating all subsets and the current subset being constructed.
Key Insight
The result list collects all subsets found during recursion, while the temporary subset list represents the current path in the decision tree. Keeping these separate allows efficient backtracking and final output construction.
Interview Quick-Check
Core Logic
The result list stores all subsets, and the temporary subset list tracks the current combination being explored.
State & Boundaries
The temporary subset is modified in-place during recursion and must be copied when adding to results to avoid mutation issues.
Recursively Explore Inclusion and Exclusion of Each Element
| 6 | def dfs(i):
|
| 7 | if i >= len(nums):
|
| 8 | res.append(subset.copy())
|
| 9 | return
|
| 11 | subset.append(nums[i])
|
| 12 | dfs(i + 1)
|
| 14 | subset.pop()
|
| 15 | dfs(i + 1)
|
Objective
To systematically generate all subsets by deciding at each index whether to include or exclude the current element.
Key Insight
The recursion models the binary decision tree of subset generation. Including an element adds it to the current subset and recurses deeper. After returning, the element is removed (un-chosen) to restore state before exploring the exclusion branch. This ensures all subsets are generated without overlap or omission.
Interview Quick-Check
Core Logic
The recursive calls represent the two choices at each step: include nums[i] and recurse, then exclude nums[i] and recurse, covering all subset possibilities.
State & Boundaries
The base case occurs when the index reaches the length of nums, at which point the current subset is copied and added to the results.
Common Pitfalls & Bugs
Failing to pop the last element after the include branch leads to incorrect subsets due to shared mutable state.
Start Recursive Exploration and Return All Subsets
| 17 | dfs(0)
|
| 18 | return res |
Objective
To initiate the recursive process from the first element and return the complete list of subsets after exploration.
Key Insight
Starting recursion at index 0 triggers the full binary decision tree traversal. Returning the result after recursion completes provides the final power set.
Interview Quick-Check
Core Logic
The initial call to dfs(0) begins the exhaustive exploration of all subset combinations.
State & Boundaries
Returning the result after recursion ensures all subsets have been collected.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
subset.pop()Remove the last element to backtrack and restore state.
Popping the last element is critical to undo the previous choice, ensuring the subset list is correct for exploring the exclusion branch.
res.append(subset.copy())Add a copy of the current subset to the results list.
Copying is essential because the subset list is mutable and will be modified during backtracking; storing a copy preserves the current state.
if i >= len(nums):Check if the recursion has reached beyond the last element.
This base case signals that a complete subset has been constructed and is ready to be added to the results.
dfs(i + 1)Recursively explore subsets including nums[i].
This recursive call advances the index, continuing the exploration with nums[i] included.
dfs(i + 1)Recursively explore subsets excluding nums[i].
This call explores the alternative decision path where nums[i] is not included, ensuring all subsets are generated.
res = []Initialize the list to store all subsets.
This list accumulates every subset found during the recursive exploration, forming the final output.
subset = []Initialize the temporary list to build subsets incrementally.
This list represents the current subset path in the recursion and is modified as elements are included or excluded.
subset.append(nums[i])Include nums[i] in the current subset.
Adding the current element models the decision to include it in the subset, enabling exploration of subsets containing nums[i].
dfs(0)Start the recursive subset exploration from index 0.
This initial call triggers the full backtracking process covering all elements.
def dfs(i):Define the recursive function to explore subsets starting from index i.
Encapsulating the recursive logic allows systematic exploration of all inclusion/exclusion decisions for elements from index i onward.
returnReturn from the recursion after adding the subset.
This terminates the current recursive path, preventing further exploration beyond the array bounds.
return resReturn the complete list of subsets after recursion finishes.
Returning the results here provides the final answer after all recursive exploration is complete.
Test Your Understanding
Why is it necessary to 'un-choose' (pop) the last element after the recursive call that includes it?
Because the subset list is shared across recursive calls, popping restores the state to explore the alternative branch where the element is excluded, ensuring no contamination between branches and correct generation of all subsets.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Subsets from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Subsets drill