Subsets II - Solution & Explanation
Problem Statement
Given an integer array nums that may contain duplicates, 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,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10
Approach Overview
Problem Overview: Given an integer array that may contain duplicate values, generate all possible subsets (the power set) while ensuring the result does not contain duplicate subsets. The main challenge is handling repeated elements so the same subset is not generated multiple times.
Approach 1: Backtracking with Sorting (O(n·2^n) time, O(n) extra space)
This approach uses backtracking to explore every subset possibility while preventing duplicates during recursion. First, sort the array so duplicate elements appear next to each other. During the recursive DFS, iterate from the current index and build the subset step by step. When encountering a duplicate value at the same recursion depth, skip it using a condition like if (i > start && nums[i] == nums[i-1]) continue. This ensures the algorithm only uses the first occurrence of each duplicate at a given level. The recursion tree explores include/exclude decisions and builds subsets incrementally. Time complexity is O(n·2^n) because up to 2^n subsets are generated and each subset copy may cost O(n). Space complexity is O(n) for the recursion stack (excluding output). This is the most common and interview-friendly solution.
Approach 2: Iterative Subset Construction (O(n·2^n) time, O(n·2^n) space)
This method builds subsets iteratively instead of recursion. Start with a result list containing an empty subset. Sort the array first so duplicates can be detected. For each number, iterate through the existing subsets and append the current number to create new subsets. When the current number is a duplicate of the previous one, only extend the subsets that were added in the previous step instead of all subsets. Tracking the starting index of newly created subsets prevents duplicate combinations. This technique treats subset generation as incremental expansion of the result list. Time complexity remains O(n·2^n) because every element can double the number of subsets. Space complexity is O(n·2^n) since all subsets are stored explicitly.
Both solutions rely on sorting the input array, a common pattern when working with duplicates in array problems. Some implementations also demonstrate subset generation using bit manipulation, but handling duplicates with bit masks typically requires additional filtering and is less practical here.
Recommended for interviews: Backtracking with sorting is the expected solution. It clearly demonstrates recursion, pruning, and duplicate handling using sorted input. Interviewers often want to see how you avoid generating duplicate subsets instead of filtering them afterward. The iterative construction method is also valid and useful if you prefer non-recursive solutions, but the backtracking approach better demonstrates algorithmic reasoning.
Approach 1: Approach 1: Backtracking with Sorting
In this approach, the problem of subsets with duplicates is solved by first sorting the array. This assists in easily identifying and omitting duplicates. The backtracking method is utilized to construct all possible subsets, ensuring no duplicate subsets are generated by skipping duplicate numbers during recursive backtracking.
The solution uses a sorting-based backtracking method. The array is sorted to handle duplicates easily. A recursive backtracking function is used to generate subsets. Before adding a number to the current subset, we check whether it is a duplicate of the previously considered number in the same recursion level. This avoids generating duplicate subsets.
Complexity
The time complexity of this solution is O(2^n * n) due to the number of subsets (2^n) and time taken to convert each subset to the result. The space complexity is O(n), where n is the length of the array, due to the space required for the subset building.
Approach 2: Approach 2: Iterative Subset Construction
This approach iteratively constructs the power set by extending previously generated sets with each new number. During the process, duplicates are skipped by comparing the current number with the previous one. This ensures subsets generated in each iteration are unique.
The C solution utilizes iterative sets through a sorted array. It dynamically expands the subsets using the current number while bypassing duplicates by monitoring the indices of additions, skipping similar additions through index boundaries.
Complexity
The time complexity is O(2^n * n); space is O(2^n * n) as it iteratively builds the power set using subsets directly.
Approach 3: Sorting + DFS
We can first sort the array nums to facilitate deduplication.
Then, we design a function dfs(i), which represents the current search for subsets starting from the i-th element. The execution logic of the function dfs(i) is as follows:
If i geq n, it means all elements have been searched, add the current subset to the answer array, and end the recursion.
If i < n, add the i-th element to the subset, execute dfs(i + 1), then remove the i-th element from the subset. Next, we check if the i-th element is the same as the next element. If they are the same, skip the element in a loop until we find the first element different from the i-th element, then execute dfs(i + 1).
Finally, we only need to call dfs(0) and return the answer array.
The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Approach 4: Sorting + Binary Enumeration
Similar to Solution 1, we first sort the array nums to facilitate deduplication.
Next, we enumerate a binary number mask in the range [0, 2^n), where the binary representation of mask is an n-bit bit string. If the i-th bit of mask is 1, it means selecting nums[i], and 0 means not selecting nums[i]. Note that if the (i - 1)-th bit of mask is 0 and nums[i] = nums[i - 1], it means that the i-th element is the same as the (i - 1)-th element in the current enumeration scheme. To avoid duplication, we skip this case. Otherwise, we add the subset corresponding to mask to the answer array.
After the enumeration, we return the answer array.
The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Sorting | The time complexity of this solution is O(2^n * n) due to the number of subsets (2^n) and time taken to convert each subset to the result. The space complexity is O(n), where n is the length of the array, due to the space required for the subset building. |
| Approach 2: Iterative Subset Construction | The time complexity is O(2^n * n); space is O(2^n * n) as it iteratively builds the power set using subsets directly. |
| Sorting + DFS | — |
| Sorting + Binary Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Sorting | O(n·2^n) | O(n) (excluding output) | Best for interviews. Clean recursion and easy duplicate skipping after sorting. |
| Iterative Subset Construction | O(n·2^n) | O(n·2^n) | Useful when avoiding recursion or when building subsets step-by-step iteratively. |
Video Solution
Subsets II - Backtracking - Leetcode 90 - Python • NeetCode • 171,047 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Subsets II easy or hard?
How to solve Subsets II in O(n)?
What is the best approach for Subsets II?
What data structure is used in Subsets II?
What is the time complexity of Subsets II?
Subsets II Python or Java solution approach?
Is Subsets II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Subsets II with our built-in code editor and test cases.
Practice on FleetCode