602. Every Subset, No Repeats
A bakery sells sprinkles in jars, and some jars hold the same flavour code. The array nums lists the flavour code of each jar; a code may appear several times. A mix is a selection of jars, and two mixes are the same when they use the same flavours the same number of times, whichever jars were picked.
Return every different mix exactly once, including the empty mix. Mixes may be returned in any order and the codes inside a mix may be in any order.
The number of different mixes can be far smaller than 2^n, so avoid generating duplicates and filtering them afterwards.
Example 1
- Input:
- nums = [2,2,6]
- Output:
- [[],[2],[2,2],[2,2,6],[2,6],[6]]
- Explanation:
The mixes are empty,
[2],[6],[2, 2],[2, 6]and[2, 2, 6]: six in total instead of eight.
Example 2
- Input:
- nums = [1,1]
- Output:
- [[],[1],[1,1]]
- Explanation:
Only three different mixes exist: empty,
[1]and[1, 1].
Example 3
- Input:
- nums = [-3,4,-3,4]
- Output:
- [[],[-3],[-3,-3],[-3,-3,4],[-3,-3,4,4],[-3,4],[-3,4,4],[4],[4,4]]
- Explanation:
Two flavours, each owned twice, give 3 * 3 = 9 different mixes.
Constraints
- 0 ≤
nums.length≤ 8 - -5 ≤
nums[i]≤ 5 - Values may repeat.
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(n * 2^n)
- Space
- O(n)