本文共 2408 字，大约阅读时间需要 8 分钟。

题目描述： Given a collection of integers that might contain duplicates, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is: [   [2],   [1],   [1,2,2],   [2,2],   [1,2],   []

]

分析：

在上一题    的基础上，本题允许集合中包含重复元素，

与上题类似，先把相应的二叉树画出来，以集合{6,8,8}为例，二叉树如下：

注意到处理第三个元素8时，因为前面已经处理了一次8，所有第三层中，我们只在已经添加过8的集合{6,8}、{8}上再添加8，而没有在集合{6}, {}上添加8（画叉的那个分支），假设下面还有一个8，那么我们只在第四层的包含两个8的集合{6,8,8}、{8,8}上选择添加8（当然，也要有“不选择”这个分支），其它都只有“不选择”这一个分支。终上所述，dfs时，如果当前处理的数字之前总共出现了k次，那么我们要处理的集合中必须包含k个该元素，即：已经包含了k个该元素的集合，有“选择”和“不选择”两个分支，而其他的集合只有“不选择”这一个分支。代码如下：

python代码：

class Solution(object):    def subsetsWithDup(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        self.sub_sets=[]        self.sub_set=[]        nums.sort()        self.dfs(nums,0)        return self.sub_sets            def dfs(self,nums,index):        if index==len(nums):            temp=self.sub_set[:]#通过切片，生成sub_set的拷贝，这一步很重要！！！            self.sub_sets.append(temp)#将生成的拷贝追加到sub_sets里            return         firstSame=index        while (firstSame>=0 and nums[firstSame]==nums[index]):            firstSame-=1        firstSame+=1 #firstSame是第一个与nums[index]相同数字的位置        k=index-firstSame # k表示和nums[index]相同数字的个数，不包含自己        if k==0 or (len(self.sub_set)>=k and self.sub_set[len(self.sub_set)-k]==nums[index]):            #选择nums[index]            self.sub_set.append(nums[index])            self.dfs(nums,index+1)            self.sub_set.pop()        #不选择nums[index]        self.dfs(nums,index+1)

C++代码：

class Solution {private:    vector
   
    
     >sub_sets;public:    vector
     
      
       > subsetsWithDup(vector
       
        & nums) {       sub_sets.clear();       sort(nums.begin(),nums.end());       vector
        
         sub_set; dfs(nums,0,sub_set); return sub_sets; } void dfs(vector
         
          &nums,int index,vector
          
           &sub_set) { if(index==nums.size()) { sub_sets.push_back(sub_set); return; } int firstSame=index; while(firstSame>=0&&nums[firstSame]==nums[index]) { firstSame--; } firstSame++;//firstSame是第一个与nums[index]相同数字的位置 int k=index-firstSame;//和nums[index]相同数字的个数，不包含自己 if(k==0||(sub_set.size()>=k && sub_set[sub_set.size()-k]==nums[index])) { //选择nums[index] sub_set.push_back(nums[index]); dfs(nums,index+1,sub_set); sub_set.pop_back(); } //不选择nums[index] dfs(nums,index+1,sub_set); }};