Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:


Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Difficulty: interview

Starter code:

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:
     def subsetsWithDup(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         def dfs(idx, path):
             subsets.append(path)
             
             for i in range(idx, len(nums)):
                 if i > idx and nums[i] == nums[i-1]:
                     continue
                 dfs(i + 1, path + [nums[i]])     
         nums.sort()
         subsets = []
         dfs(0, [])
         
         return subsets
         
         
         
         
             
             
                 
         
             
                 


class Solution:
     def subsets(self, nums):
         if len(nums) == 0:
             return [[]]
         ret = []
         for i, n in enumerate(nums):
             if i > 0 and n == nums[i - 1]:
                 continue
             for s in self.subsets(nums[i + 1:]):
                 ret.append([n] + s)
         return [[]] + ret
     def subsetsWithDup(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         nums.sort()
         return self.subsets(nums)

class Solution:
     def subsetsWithDup(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         result = []
         res = []
         
         self.df(nums, 0, result, res)
         return res
     
     def df(self, nums, idx, result, res):
         if idx > len(nums):
             return
         if result not in res:
             res.append(result)
         
         for i in range(idx, len(nums)):
             self.df(nums, i+1, sorted(result + [nums[i]]), res)

class Solution:
     def subsetsWithDup(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         def dfs(depth, start, cur):
             if cur not in res:
                 res.append(cur)
             if depth == len(nums):
                 return 
             for i in range(start, len(nums)):
                 dfs(depth + 1, i + 1, cur + [nums[i]])
         
         nums.sort()
         res = []
         dfs(0, 0, [])
         return list(res)

class Solution:
     def subsetsWithDup(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         
         def backtrack(nums, start, tmp, res):
             res.append(tmp[:])
             
             for i in range(start, len(nums)):
                 if i>start and nums[i] == nums[i-1]:
                     continue
                 else:
                     tmp.append(nums[i])
                     backtrack(nums, i+1, tmp, res)
                     del tmp[-1]
                     
         res = list()
         backtrack(sorted(nums), 0, [], res)
         return res 


class Solution:
     def subsetsWithDup(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         nums = sorted(nums)
         res = [[]]
         self._helpFun(nums,  res, [])
         return(res)
     
     def _helpFun(self, nums, res, curr):
         if not nums:
             if curr not in res:
                 res.append(curr)
             return
         
         for i in range(len(nums)):
             newCurr = curr + [nums[i]]
             if newCurr not in res:
                 res.append(newCurr)
             
             self._helpFun(nums[i+1:], res, newCurr )