Given an integer array nums that may contain duplicates, return all possible subsets. The answer must not contain two subsets with the same elements (as multisets), so [1,2] and [2,1] count as the same subset. Return them in any order.
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force builds all 2^n subsets, sorts each and stores them in a set to remove duplicates: correct, but it does extra sorting and hashing. Duplicates appear because, at some position, we start a branch with a value that an earlier sibling branch already started with. After sorting nums, equal values sit together, so the rule is simple: at each recursion level, use each distinct value only once as the next pick. That is the check j > start and nums[j] == nums[j - 1]. We still allow [2,2], because the second 2 is picked at a deeper level, not as a sibling.
Algorithm
- Sort
nums. - Define
backtrack(start): add a copy ofpathto the result. - Loop
jfromstart; ifj > startandnums[j] == nums[j - 1], skip it. - Otherwise append
nums[j], callbacktrack(j + 1), and pop. - Call
backtrack(0)and return the result.
O(n * 2^n)Space: O(n) recursion depth, plus the outputj > start, not j > 0. Using j > 0 also blocks picking the second 2 one level deeper, so [2,2] and [1,2,2] go missing. The same skip rule is reused in Combination Sum II and Permutations II.class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() # equal values become neighbours res, path = [], []Β def backtrack(start): res.append(path[:]) for j in range(start, len(nums)): if j > start and nums[j] == nums[j - 1]: continue # same value as a sibling branch path.append(nums[j]) backtrack(j + 1) path.pop()Β backtrack(0) return res