Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1: Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
- code
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
def backtracking(nums, path, res):
path = sorted(path)
if path not in res:
res.append(path)
for i in range(len(nums)):
backtracking(nums[i+1:], path + [nums[i]], res)
backtracking(nums, [], res)
return res
- code
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = [[]]
nums.sort()
for i in range(len(nums)):
if i == 0 or nums[i] != nums[i-1]:
l = len(res)
for x in range(len(res)-l, len(res)):
res.append(res[x] + [nums[i]])
return res
if S[i] is same to S[i - 1], then it needn’t to be added to all of the subset, just add it to the last l subsets which are created by adding S[i - 1]