756. Subsets II (With Duplicates)

Given an integer array nums that may contain duplicates, return all DISTINCT subsets (the distinct power set). The output must be canonical:
1. Each subset's elements are in non-decreasing order.
2. The list of subsets is sorted first by length (shortest first), then lexicographically.
Duplicate subsets must appear only once.

Input: An integer array nums.

Output: Return the canonical list of distinct subsets.

Examples

Input: [1,2,2]
Output: [[],[1],[2],[1,2],[2,2],[1,2,2]]
Explanation: Distinct subsets only; duplicates suppressed.

Input: [0]
Output: [[],[0]]
Explanation: Two subsets.

Input: [4,4,4,1,4]
Output: [[],[1],[4],[1,4],[4,4],[1,4,4],[4,4,4],[1,4,4,4],[4,4,4,4],[1,4,4,4,4]]
Explanation: Distinct subsets when sorting and deduping (4 appears 4 times, 1 once).

Constraints

• 1 <= nums.length <= 10
• -100 <= nums[i] <= 100

Asked by