1. Problem Statement (Simple Explanation)
You’re given an integer array nums that may contain duplicates.
You must return all possible subsets (the power set) of nums, with the constraint:
The output must not contain duplicate subsets.
Subsets can be in any order.
1 <= nums.length <= 10, so maximum 210 = 1024 subsets.
2. Examples
Example 1:
Input: nums = [1,2,2]
All subsets (unique):
[]
[1]
[2]
[1,2]
[2,2]
[1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Subsets:
[]
[0]
Output: [[],[0]]
3. Approach – Backtracking with Duplicate Skipping
This is similar to Problem 78 (Subsets), but nums can have duplicates, so we must avoid generating duplicate subsets.
Key Idea:
Sort the array nums.
This groups duplicates together and makes it easier to skip them.
Use backtracking to build subsets:
Maintain:
current subset (list).
start index where we choose next element.
At each recursive call:
Add a copy of current to result (every state is a valid subset).
Loop i from start to len(nums)-1:
Skip duplicates at the same recursion depth:
if i > start and nums[i] == nums[i-1]:
continue
Include nums[i] in current.
Recurse with start = i + 1.
Backtrack (remove last element).
The i > start check ensures we only skip duplicate choices at the same level of the recursion tree, which avoids generating the same subset multiple times.
Pseudo-code:
Complexity:
Let n = len(nums):
The total number of unique subsets is at most 2n.
Time: O(n * 2n) (each subset construction is O(n) and there are up to 2n).
Space:
O(n) recursion depth and current subset.
Output itself is O(n * 2n).
Given n <= 10, this is very efficient.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment