Subsets
MedPrompt
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach builds the solution iteratively. It starts with an empty subset in the result list. Then, it iterates through each number in the input array. For each number, it goes through all the subsets currently in the result list, creates a new subset by adding the current number to each of them, and adds these new subsets to the result list.
Algorithm
- Initialize a list of lists
resultand add an empty list to it. - For each number
numin the input arraynums:- Get the current number of subsets in
result. - Iterate through the existing subsets (from index 0 to the original size).
- For each existing subset, create a new subset by copying it and adding
num. - Add this new subset to the
resultlist.
- Get the current number of subsets in
- Return
result.
Walkthrough
The algorithm begins by initializing the result list with just the empty set. It then iterates through each number in the input nums array. In each iteration, it effectively doubles the number of subsets in the result list. It does this by iterating through the subsets that have been computed so far, and for each one, it creates a new subset that is a copy of the existing one plus the current number. These newly formed subsets are then added to the result list.
For example, with nums = [1, 2]:
- Start with
result = [[]]. - Process
1: Create a new subset[1]from[]. Add it.resultis now[[], [1]]. - Process
2: Create new subsets[2](from[]) and[1, 2](from[1]). Add them.resultis now[[], [1], [2], [1, 2]].
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 num : nums) { int currentSize = result.size(); for (int i = 0; i < currentSize; i++) { // Create a new subset from an existing one and add the current number List<Integer> newSubset = new ArrayList<>(result.get(i)); newSubset.add(num); result.add(newSubset); } } return result; }}Complexity
Time
O(n * 2^n)
Space
O(n * 2^n)
Trade-offs
Pros
- Intuitive and easy to understand.
- Avoids recursion, so there's no risk of stack overflow.
Cons
- Can be less performant due to the overhead of creating many new list objects and copying elements in each step.
This is a classic recursive approach to generate all combinations. We use a helper function that builds a subset. At each step, we have two choices for an element: either include it in the current subset or not. The backtracking algorithm explores all these possible choices to form all subsets.
Algorithm
- Define a recursive function
backtrack(start, currentSubset, nums, result). - In the main function, initialize an empty
resultlist and callbacktrack(0, new ArrayList<>(), nums, result). - Inside
backtrack:- Add a copy of
currentSubsetto theresultlist. - Loop with an index
ifromstartto the end of thenumsarray.- Add the element
nums[i]tocurrentSubset. - Make a recursive call:
backtrack(i + 1, currentSubset, nums, result). - Remove the last element from
currentSubsetto backtrack.
- Add the element
- Add a copy of
Walkthrough
The core of this approach is a recursive helper function, often called backtrack. This function is responsible for building the subsets. It takes the current position start in the nums array and the currentSubset being built as parameters.
At each call, we first add the current state of currentSubset to our final result list. This captures subsets of all possible lengths. Then, we loop from the start index to the end of the array. In each iteration of the loop, we 'choose' an element by adding it to currentSubset, then 'explore' further possibilities by making a recursive call with the next index (i + 1). After the recursive call returns, we 'unchoose' the element by removing it from currentSubset. This 'unchoosing' step is the backtracking part, which allows us to explore different branches of the solution space, such as subsets that do not include the current element but include subsequent ones.
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(0, new ArrayList<>(), nums, result); return result; } private void backtrack(int start, List<Integer> currentSubset, int[] nums, List<List<Integer>> result) { // Add the current combination to the result list result.add(new ArrayList<>(currentSubset)); for (int i = start; i < nums.length; i++) { // Include the element nums[i] currentSubset.add(nums[i]); // Explore subsets starting from the next element backtrack(i + 1, currentSubset, nums, result); // Backtrack: remove the element to explore other subsets currentSubset.remove(currentSubset.size() - 1); } }}Complexity
Time
O(n * 2^n)
Space
O(n * 2^n)
Trade-offs
Pros
- A standard and elegant pattern for solving many combinatorial problems.
- It is a very generalizable approach that can be adapted for similar problems like combinations and permutations.
Cons
- Recursion can have a higher overhead than iterative solutions.
- The concept of backtracking might be less intuitive for beginners.
This approach leverages the fact that for n elements, there are 2^n possible subsets. Each subset can be represented by an n-bit integer (a bitmask). If the j-th bit is 1, the j-th element of the input array is included in the subset; otherwise, it's not.
Algorithm
- Let
nbe the length ofnums. - Calculate the total number of subsets,
numSubsets = 2^n. - Initialize an empty list of lists
result. - Loop with an integer
ifrom0tonumSubsets - 1.- This
iwill act as a bitmask. - Initialize an empty list
currentSubset. - Loop with an integer
jfrom0ton - 1.- Check if the
j-th bit is set iniusing(i >> j & 1) == 1. - If it is, add the element
nums[j]tocurrentSubset.
- Check if the
- After the inner loop, add
currentSubsettoresult.
- This
- Return
result.
Walkthrough
The key idea is to map each subset to a unique binary number. For an input array of size n, we can represent all 2^n subsets using numbers from 0 to 2^n - 1. Each of these numbers serves as a bitmask of length n.
We iterate from i = 0 to 2^n - 1. For each i, we construct a corresponding subset. We do this by iterating through the bits of i from j = 0 to n-1. If the j-th bit of i is set to 1, it signifies that the element nums[j] should be included in the current subset. We can check the j-th bit using the bitwise operation (i >> j) & 1.
This method is very direct and avoids recursion. It systematically generates all subsets based on the binary representation of numbers.
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; int numSubsets = 1 << n; // This is 2^n // Iterate from 0 to 2^n - 1 for (int i = 0; i < numSubsets; i++) { List<Integer> currentSubset = new ArrayList<>(); for (int j = 0; j < n; j++) { // Check if the j-th bit in i is set if ((i >> j & 1) == 1) { currentSubset.add(nums[j]); } } result.add(currentSubset); } return result; }}Complexity
Time
O(n * 2^n)
Space
O(n * 2^n)
Trade-offs
Pros
- Very efficient in practice due to fast bitwise operations and an iterative structure.
- Conceptually clean and concise for those familiar with bit manipulation.
- Generates subsets in a predictable, lexicographically sorted order (based on the bitmask).
Cons
- The approach is limited by the size of standard integer types (e.g.,
longfor up ton=64), though this is not an issue for the given constraints.
- The approach is limited by the size of standard integer types (e.g.,
- Might be less intuitive if one is not comfortable with bit manipulation.
Solutions
Solution
class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> t = new ArrayList<>();private int[] nums;public List<List<Integer>> subsets(int[] nums) { this.nums = nums; dfs(0); return ans; }private void dfs(int i) { if (i == nums.length) { ans.add(new ArrayList<>(t)); return; } dfs(i + 1); t.add(nums[i]); dfs(i + 1); t.remove(t.size() - 1); }}class Solution {public: vector<vector<int>> subsets(vector<int> &nums) { vector<vector<int>> ans; vector<int> t; function<void(int)> dfs = [&](int i) -> void { if (i == nums.size()) { ans.push_back(t); return; } dfs(i + 1); t.push_back(nums[i]); dfs(i + 1); t.pop_back(); }; dfs(0); return ans; }};from typing import List class Solution : # bfs def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: if not nums : return [[]] nums . sort () # sort() not necessary if no duplicates result = [[]] for num in nums : result += [ subset + [ num ] for subset in result ] return result class Solution : # dfs def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( u , t ): ans . append ( t [:]) # or, t.copy() for i in range ( u , len ( nums )): t . append ( nums [ i ]) dfs ( i + 1 , t ) t . pop () ans = [] nums . sort () # sort() not necessary if no duplicates dfs ( 0 , []) return ans class Solution : # dfs, just pass down the final path def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( nums , index , path , ans ): ans . append ( path ) [ dfs ( nums , i + 1 , path + [ nums [ i ]], ans ) for i in range ( index , len ( nums ))] ans = [] dfs ( nums , 0 , [], ans ) return ans class Solution : # dfs, but running slower, since need to reference from parent method for 'nums' and 'ans' def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( index , path ): ans . append ( path ) [ dfs ( i + 1 , path + [ nums [ i ]]) for i in range ( index , len ( nums ))] ans = [] dfs ( 0 , []) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.