90. Subsets II
You receive an integer array nums that may contain repeated values. Return every distinct subset of nums — two subsets count as the same if they use the same values with the same multiplicities, regardless of which original positions supplied them. The empty subset is always included.
To make the answer unique, present it in canonical form: sort the elements inside each subset in non-decreasing order, then list the subsets in lexicographic order as sequences (comparing element by element numerically, with a subset that is a prefix of another coming first). Under that ordering the empty subset always leads.
Example 1:
Input: nums = [1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Explanation: Although the two 2s sit at different positions, [1,2] can only appear once. Six distinct subsets exist, listed lexicographically: prefixes first, smaller elements first.
Example 2:
Input: nums = [0]
Output: [[], [0]]
Explanation: A single element yields exactly two subsets: the empty one and the whole array.
Constraints:
- 1 ≤ nums.length ≤ 10
- -10 ≤ nums[i] ≤ 10
Hints:
Sort first. Once equal values sit next to each other, duplicate subsets can only arise one way: choosing the *same value* at the *same branching point* of your search from two different positions.
In a backtracking scan that extends the current subset with nums[i], nums[i+1], …: skip index i whenever i is past the branch's first option and nums[i] equals nums[i−1]. That one guard emits every distinct subset exactly once — and, on a sorted array, already in the required lexicographic order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 2]
Expected output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]