The problem
Given an array nums that may contain repeated values, return every different subset, in any order. Two subsets holding the same values the same number of times count as one.
Examples
01
- Input
nums = [1, 2, 2]
- Output
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
02
- Input
nums = [0]
- Output
[[], [0]]
Constraints
- 1 ≤ nums.length ≤ 10
- −10 ≤ nums[i] ≤ 10
The idea
Sort first, so equal values sit side by side. Then build each subset by choosing its elements in position order: from a subset, try adding each later element in turn.
The repeats come from choosing “the first 2” and “the second 2” for the same spot, which gives the same subset twice. So, among the options for one spot, skip an element equal to the one just before it. A later 2 can still be added after an earlier 2 — that is a different spot.
- Time
- O(n · 2ⁿ)
- Space
- O(n) besides the answer
Solution · every language run against every case
class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() # equal values side by side out, cur = [], [] def extend(start): # cur is a subset; try adding each later value to it out.append(cur[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # the same value in the same place would repeat a subset cur.append(nums[i]) extend(i + 1) cur.pop() extend(0) return out