Subsets II
Problem
Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets. The solution set must not contain duplicate subsets. Return the solution in any order.
- 1 ≤ nums.length ≤ 10
- −10 ≤ nums[i] ≤ 10
Example
nums = [1,2,2][[],[1],[1,2],[1,2,2],[2],[2,2]]The brute-force approach generates all subsets without considering duplicates, resulting in duplicate subsets like [1,2] appearing multiple times. The algorithm first sorts nums to group duplicates together. It then uses backtracking to explore subsets, carefully skipping over duplicate elements at the same recursion depth to avoid generating duplicate subsets. For example, after including the first '2', the algorithm skips the second '2' at the same level to prevent duplicate subsets. This pruning ensures each unique subset is generated exactly once.
Approach
Straightforward Solution
A naive backtracking approach generates all subsets by including or excluding each element, resulting in 2^n subsets. However, with duplicates, this approach produces duplicate subsets, requiring post-processing or extra checks, which is inefficient.
Core Observation
The fundamental challenge is to generate all subsets while avoiding duplicates caused by repeated elements. Sorting the input groups duplicates, enabling the algorithm to detect and skip over repeated elements during recursion to prevent duplicate subsets.
Path to Optimal
Sorting the array is the key insight, as it places duplicates consecutively. During backtracking, when deciding whether to include or exclude an element, the algorithm skips over duplicates at the same recursion depth by advancing the index past repeated values. This pruning avoids generating duplicate subsets without extra storage or post-filtering.
Optimal Approach
The algorithm sorts nums, then uses a recursive backtracking function that explores subsets by including or excluding elements. Before recursing on the exclusion path, it advances the index to skip duplicates. This ensures that subsets differing only by the position of duplicate elements are not generated multiple times. The result is a complete, duplicate-free set of subsets generated in O(2^n) time, which is optimal for subset enumeration.
Time
O(2^n)
The algorithm explores all unique subsets. In the worst case with no duplicates, there are 2^n subsets. Sorting takes O(n log n), which is dominated by the subset generation.
Space
O(n)
The recursion stack and the temporary subset list use O(n) space. The output list size is O(2^n), but this is not counted as auxiliary space.
Pattern Spotlight
Backtracking (State Restoration with Duplicate Skipping)
When generating subsets with duplicates, sort the input and skip over duplicate elements at the same recursion depth to prune redundant branches, ensuring each unique subset is generated exactly once without extra post-processing.
Solution
| 1 | class Solution:
|
| 2 | def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
|
| 3 | res = []
|
| 4 | nums.sort()
|
| 5 |
|
| 6 | def backtrack(i, subset):
|
| 7 | if i == len(nums):
|
| 8 | res.append(subset.copy())
|
| 9 | return
|
| 10 |
|
| 11 | subset.append(nums[i])
|
| 12 | backtrack(i + 1, subset)
|
| 13 | subset.pop()
|
| 14 |
|
| 15 | while i + 1 < len(nums) and nums[i] == nums[i + 1]:
|
| 16 | i += 1
|
| 17 | backtrack(i + 1, subset)
|
| 18 |
|
| 19 | backtrack(0, [])
|
| 20 | return res |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.Arrays; |
| 3 | import java.util.List; |
| 4 | |
| 5 | class Solution { |
| 6 | public List<List<Integer>> subsetsWithDup(int[] nums) { |
| 7 | List<List<Integer>> res = new ArrayList<>(); |
| 8 | Arrays.sort(nums); |
| 9 | backtrack(nums, 0, new ArrayList<>(), res); |
| 10 | return res; |
| 11 | } |
| 12 | |
| 13 | private void backtrack(int[] nums, int i, List<Integer> subset, List<List<Integer>> res) { |
| 14 | if (i == nums.length) { |
| 15 | res.add(new ArrayList<>(subset)); |
| 16 | return; |
| 17 | } |
| 18 | |
| 19 | subset.add(nums[i]); |
| 20 | backtrack(nums, i + 1, subset, res); |
| 21 | subset.remove(subset.size() - 1); |
| 22 | |
| 23 | while (i + 1 < nums.length && nums[i] == nums[i + 1]) { |
| 24 | i++; |
| 25 | } |
| 26 | backtrack(nums, i + 1, subset, res); |
| 27 | } |
| 28 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<vector<int>> subsetsWithDup(vector<int>& nums) { |
| 9 | vector<vector<int>> res; |
| 10 | sort(nums.begin(), nums.end()); |
| 11 | vector<int> subset; |
| 12 | backtrack(nums, 0, subset, res); |
| 13 | return res; |
| 14 | } |
| 15 | |
| 16 | private: |
| 17 | void backtrack(const vector<int>& nums, int i, vector<int>& subset, vector<vector<int>>& res) { |
| 18 | if (i == (int)nums.size()) { |
| 19 | res.push_back(subset); |
| 20 | return; |
| 21 | } |
| 22 | |
| 23 | subset.push_back(nums[i]); |
| 24 | backtrack(nums, i + 1, subset, res); |
| 25 | subset.pop_back(); |
| 26 | |
| 27 | while (i + 1 < (int)nums.size() && nums[i] == nums[i + 1]) { |
| 28 | i++; |
| 29 | } |
| 30 | backtrack(nums, i + 1, subset, res); |
| 31 | } |
| 32 | }; |
| 1 | var subsetsWithDup = function(nums) { |
| 2 | const res = []; |
| 3 | nums.sort((a, b) => a - b); |
| 4 | |
| 5 | function backtrack(i, subset) { |
| 6 | if (i === nums.length) { |
| 7 | res.push(subset.slice()); |
| 8 | return; |
| 9 | } |
| 10 | |
| 11 | subset.push(nums[i]); |
| 12 | backtrack(i + 1, subset); |
| 13 | subset.pop(); |
| 14 | |
| 15 | while (i + 1 < nums.length && nums[i] === nums[i + 1]) { |
| 16 | i++; |
| 17 | } |
| 18 | backtrack(i + 1, subset); |
| 19 | } |
| 20 | |
| 21 | backtrack(0, []); |
| 22 | return res; |
| 23 | }; |
Step-by-Step Solution
Sort Input to Group Duplicates for Pruning
| 4 | nums.sort()
|
Objective
To arrange the input array so that duplicate elements are adjacent, enabling efficient duplicate skipping during backtracking.
Key Insight
Sorting is a crucial preprocessing step that clusters duplicates together. This ordering allows the backtracking algorithm to detect consecutive duplicates easily and skip them at the same recursion depth, preventing redundant subset generation. Without sorting, duplicates would be scattered, making pruning impossible or inefficient.
Interview Quick-Check
Core Logic
Sorting groups duplicates, which is essential for the pruning logic that skips repeated elements during recursion.
Common Pitfalls & Bugs
Failing to sort leads to duplicate subsets because the algorithm cannot detect duplicates efficiently.
Explore Subsets via Backtracking with Duplicate Skipping
| 6 | def backtrack(i, subset):
|
| 7 | if i == len(nums):
|
| 8 | res.append(subset.copy())
|
| 9 | return
|
| 11 | subset.append(nums[i])
|
| 12 | backtrack(i + 1, subset)
|
| 13 | subset.pop()
|
| 15 | while i + 1 < len(nums) and nums[i] == nums[i + 1]:
|
| 16 | i += 1
|
| 17 | backtrack(i + 1, subset)
|
Objective
To recursively build subsets by deciding whether to include each element, while skipping duplicates to avoid redundant subsets.
Key Insight
The backtracking function explores two paths at each index: include the current element or exclude it. After including, it recurses to the next index. After excluding, it advances the index past any duplicates before recursing. This skipping ensures that subsets differing only by the choice of identical elements at the same recursion level are not duplicated. The use of subset.copy() when adding to results preserves state across recursive calls.
Interview Quick-Check
Core Logic
The algorithm uses recursion to explore all subset combinations, pruning duplicate branches by skipping over repeated elements after exclusion.
State & Boundaries
The base case occurs when the index reaches the length of nums, at which point the current subset is added to the results.
Common Pitfalls & Bugs
Not skipping duplicates after exclusion leads to duplicate subsets; forgetting to copy the subset before appending causes shared state bugs.
Initiate Backtracking and Return All Unique Subsets
| 3 | res = []
|
| 19 | backtrack(0, [])
|
| 20 | return res |
Objective
To start the recursive exploration from the first element and return the collected unique subsets.
Key Insight
The initial call to backtrack starts the recursion with an empty subset and index zero. After the recursion completes, the accumulated results contain all unique subsets. This step connects the recursive exploration to the final output.
Interview Quick-Check
Core Logic
Starting recursion at index 0 with an empty subset ensures all subsets are explored.
State & Boundaries
Returning the results after recursion completes provides the final answer.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
res.append(subset.copy())Add a copy of the current subset to the results list.
Copying the subset is critical to preserve the current state, as the subset list is mutated during backtracking; without copying, all results would reference the same list.
subset.pop()Remove the current element to backtrack and restore state.
This 'un-choose' step is critical to restore the subset state before exploring subsets that exclude the current element, enabling correct exploration of all branches.
nums.sort()Sort the input array to group duplicate elements together.
Sorting is essential to enable the pruning logic that skips duplicates during recursion, preventing duplicate subsets.
while i + 1 < len(nums) and nums[i] == nums[i + 1]:Skip over duplicate elements to avoid generating duplicate subsets.
By advancing the index past duplicates at the same recursion depth, the algorithm prunes redundant branches that would produce identical subsets, ensuring uniqueness without extra storage.
if i == len(nums):Check if the recursion has reached the end of the input array.
This base case terminates recursion and triggers adding the current subset to the results, ensuring all subsets are eventually collected.
backtrack(i + 1, subset)Recurse to explore subsets including the current element.
This recursive call advances the index, continuing exploration with the current element included.
backtrack(i + 1, subset)Recurse to explore subsets excluding the current element and its duplicates.
This recursive call explores subsets that skip the current element and all its duplicates, ensuring no duplicate subsets are generated.
returnReturn from recursion after adding the subset.
This stops further recursion once a complete subset has been recorded, preventing unnecessary exploration beyond the array bounds.
subset.append(nums[i])Include the current element in the subset.
Adding the current element represents the 'choose' step in backtracking, exploring subsets that contain this element.
i += 1Increment the index to move past duplicates.
This loop advances the index to the next distinct element, enabling the pruning logic to work correctly.
backtrack(0, [])Start backtracking from the first element with an empty subset.
This initial call triggers the entire recursive exploration of all unique subsets starting from the beginning of the array.
def backtrack(i, subset):Define the recursive backtracking function with current index and subset state.
Encapsulating the recursion in a helper function allows clean management of the current subset and index, enabling systematic exploration of all subset possibilities.
res = []Initialize the list to store all unique subsets.
This list accumulates the final results of the backtracking process, collecting each unique subset found.
return resReturn the list of all unique subsets found.
After recursion completes, this returns the accumulated results to the caller as the final answer.
Test Your Understanding
Why does skipping duplicates at the same recursion depth prevent generating duplicate subsets?
Because duplicates are adjacent after sorting, skipping over repeated elements at the same recursion level avoids exploring branches that would produce identical subsets differing only in the position of duplicate elements, ensuring each unique subset is generated once.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Subsets II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Subsets II drill