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

        res = []
        candi = []


        def dfs(idx):

            if idx == len(nums):
                res.append(candi.copy())
                return 

            candi.append(nums[idx])
            dfs(idx + 1)

            candi.pop(-1)

            i = idx + 1
            while(i < len(nums)):
                if nums[i] == nums[idx]:
                    i+=1
                else:
                    break            
            dfs(i)

        dfs(0)      
        return res