Generate all unique subsets of an integer array that may contain duplicates.
Problem
Given an integer array nums that may contain duplicate values, return every possible unique subset of nums.
A subset can contain any number of elements from the array, including none of them. Two subsets are considered the same if they contain the same multiset of values, regardless of the order in which they were formed during search.
Return the collection of subsets in any order, with no duplicate subsets included.
Notes
- The input array may include repeated numbers.
- Each element can be used at most once in a subset because it comes from a single position in the array.
- The empty subset must be included.
Input Format
- An integer array
nums.
Output Format
- A list of all distinct subsets of
nums.
Constraints
0 <= nums.length <= 20$-10^{9}$ <= nums[i] <= $10^{9}$
Hints
- Sorting the array can make duplicate handling much easier.
- When exploring choices at the same recursion depth, avoid starting multiple branches with the same value.
- Track subsets by positions, not just by values, then remove duplicate branches carefully.
Input Format
nums: integer array that may contain duplicates.
Output Format
Return all distinct subsets of nums, including the empty subset.
Constraints
0 <= nums.length <= 20$-10^{9}$ <= nums[i] <= $10^{9}$
Example 1
Input
nums = [1,2,2]
Output
[[],[1],[2],[1,2],[2,2],[1,2,2]]
Explanation
The value 2 appears twice, so subsets that would otherwise be duplicated are included only once.
Example 2
Input
nums = [0]
Output
[[],[0]]
Explanation
There are two unique subsets: the empty subset and the subset containing the single element.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.