101
0/320
Loading content...
Given a collection of integers that may contain duplicate values, generate all distinct subsets (also known as the power set) of the collection.
The power set of a collection is the set of all possible subsets, including the empty set and the collection itself. Since the input may contain duplicate values, the resulting power set must not include any duplicate subsets—each unique combination of elements should appear exactly once.
You may return the subsets in any order, as long as no two subsets contain the same multiset of elements.
Key Insight: When an array contains duplicate elements, blindly generating all 2^n subsets will produce duplicates. The challenge lies in systematically avoiding these duplicates while still enumerating all unique combinations. Sorting the array and carefully handling consecutive duplicate values during the generation process is critical to achieving this efficiently.
nums = [1,2,2][[],[1],[2],[1,2],[2,2],[1,2,2]]The input array has 3 elements with the value 2 appearing twice. The power set contains 6 unique subsets: the empty set [], single elements [1] and [2], pairs [1,2] and [2,2], and the full set [1,2,2]. Notice that [2] appears only once despite having two 2s in the input, and there is no duplicate [1,2] subset.
nums = [0][[],[0]]For a single-element array, the power set contains exactly 2 subsets: the empty set and the set containing just that element.
nums = [1,1,2,2][[],[1],[2],[1,1],[1,2],[2,2],[1,1,2],[1,2,2],[1,1,2,2]]With two pairs of duplicates (two 1s and two 2s), we get 9 unique subsets. Each unique multiset of elements appears exactly once. For instance, [1,2] represents selecting one 1 and one 2, while [1,1,2] represents selecting both 1s and one 2.
Constraints