数组的子集: lc 78/90

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res = []
        nums = sorted(nums)
        self.dfs([], 0, nums)
        return self.res
    
    def dfs(self, cur, idx, nums):
        self.res.append(cur[:])
        for i in range(idx, len(nums)):
            # we did not explore the equivalent element before.
            # think of [1,2,2]
            # 如果第一个2没选，到第二个2的时候，不能加入到res中
            if i > idx and nums[i] == nums[i-1]:
                continue
            cur.append(nums[i])
            self.dfs(cur, i+1, nums)
            cur.pop()