Subsets II
MediumBacktracking
Given an integer array nums that may contain repeated values, return every distinct subset of it.
A subset picks some of the elements (possibly none, possibly all). Two subsets are the same if they contain the same values the same number of times, no matter which positions they were picked from, so each such subset must appear exactly once. Return the subsets in any order; the values inside a subset may also be in any order.
Example 1
- Input:
- nums = [1,2,1,2]
- Output:
- [[],[1],[1,1],[1,1,2],[1,1,2,2],[1,2],[1,2,2],[2],[2,2]]
- Explanation
- A subset is determined by how many 1s (0, 1 or 2) and how many 2s (0, 1 or 2) it holds, giving 3 x 3 = 9 distinct subsets. Picking the first 1 or the second 1 gives the same subset
[1].
Example 2
- Input:
- nums = [2,2,2]
- Output:
- [[],[2],[2,2],[2,2,2]]
- Explanation
- Three identical values give only four distinct subsets: zero, one, two or three 2s.
Example 3
- Input:
- nums = [-1,3,-1]
- Output:
- [[],[-1],[-1,-1],[-1,-1,3],[-1,3],[3]]
- Explanation
- The two -1 values behave like any other duplicate pair: 3 choices for the count of -1 times 2 choices for 3 gives 6 subsets.
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10