子集问题+去重子集II题目链接：https://leetcode-cn.com/problems/subsets-ii/给定一个可能包含重复元素的整数数组nums，返回数组所有可能的子集A（动力装置）的。解释：解集不能包含重复的子集。示例：输入：[1,2,2]输出：[[2],[1],[1,2,2],[2,2],[1,2],[]]在做这道题之前，你必须先做78.子集。这道题和78.子集的区别在于集合中有重复的元素，得到的子集一定是重复的。然后，回溯算法中的去重问题在40.组合求和二中已经有详细的讲解，是本题的套路。剧透警告，后面讲解的排列问题中的去重也是老套路，所以理解“树层去重”和“分支去重”非常重要。以例子中的[1,2,2]为例，如图：（注意集合需要先排序去重）从图中可以看出子集II，在同一棵树上重复2layer一定要过滤掉，可以在同一个分支上重复取2，因为同一个分支上的元素集合是唯一的子集！这道题其实是78.Subsets是在去重的基础上加的。对于去重，我们也在40.CombinationsumII已经说了，直接给出代码：C++代码如下：classSolution{private:vector>result;vectorpath;voidbacktracking(vector&nums,intstartIndex,vector&used){result.push_back(path);for(inti=startIndex;i0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}path.push_back(nums[i]);使用[i]=true;backtracking(nums,i+1,used);使用[i]=false;path.pop_back();}}public:vector>subsetsWithDup(vector&nums){result.clear();path.clear();vectorused(nums.size(),false);sort(nums.begin(),nums.end());//需要去重排序回溯（nums，0，使用）；returnresult；}}；使用set去重复版本。classSolution{private:vector>result;vectorpath;voidbacktracking(vector&nums,intstartIndex,vector&used){result.push_back(path);unordered_setuset;for(inti=startIndex;i>subsetsWithDup(vector&nums){result.clear();path.clear();vectorused(nums.size(),false);sort(nums.begin(),nums.end());//去重需要排序回溯(nums,0,used);returnresult;}};补充这道题也可以不使用used数组去重，因为递归时下一个startIndex是i+1而不是0。如果是满排列，每次都需要从0开始遍历。为了跳过已经入栈的元素，需要使用used。代码如下：startIndex&&nums[i]==nums[i-1]){//注意i>startIndexcontinue是在这里使用；}path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}public:vector>subsetsWithDup(vector&nums){result.clear();path.clear();sort(nums.begin(),nums.end());//去重需要排序backtracking(nums,0);returnresult;}};总结一下这道题的知识点，我们之前说过了，如果你掌握了前面提到的子集问题和去重问题，这道题应该分分钟AC。当然这道题去重的逻辑也可以这样写if(i>startIndex&&nums[i]==nums[i-1]){continue;}其他语言版本JavaclassSolution{List>result=newArrayList<>();//存放符合条件的结果集LinkedListpath=newLinkedList<>();//用于存放符合条件的结果boolean[]used;publicList>subsetsWithDup(int[]nums){if(nums.length==0){result.add(path);returnresult;}Arrays.sort(nums);used=newboolean[nums.length];subsetsWithDupHelper(nums,0);returnresult;}privatevoidsubsetsWithDupHelper(int[]nums,intstartIndex){result.add(newArrayList<>(path));if(startIndex>=nums.length){return;}for(inti=startIndex;i0&&nums[i]==nums[i-1]&&!used[i-1]){continue;}path.add(nums[i]);used[i]=true;subsetsWithDupHelper(nums,i+1);path.removeLast();used[i]=false;}}}PythonclassSolution:defsubsetsWithDup(self,nums:List[int])->List[List[int]]:res=[]#存储合格结果Collectionpath=[]#用于存储e合格的结果defbacktrack(nums,startIndex):res.append(path[:])foriinrange(startIndex,len(nums)):ifi>startIndexandnums[i]==nums[i-1]:#我们要跳过同一树层中使用的元素continuepath.append(nums[i])backtrack(nums,i+1)#recursivepath.pop()#backtrackingnums=sorted(nums)#去重需要排序回溯(nums,0)returnresGovarres[][]intfuncsubsetsWithDup(nums[]int)[][]int{res=make([][]int,0)sort.Ints(nums)dfs([]int{},nums,0)returnres}funcdfs(temp,num[]int,startint){tmp:=make([]int,len(temp))copy(tmp,temp)res=append(res,tmp)fori:=start;istart&&num[i]==num[i-1]{continue}temp=append(temp,num[i])dfs(temp,num,i+1)temp=temp[:len(temp)-1]}}JavascriptvarsubsetsWithDup=function(nums){letresult=[]letpath=[]letsortNums=nums.sort((a,b)=>{returna-b})functionbacktracing(startIndex,sortNums){result.push(path.slice(0))if(startIndex>nums.length-1){return}for(leti=startIndex;istartIndex&&nums[i]===nums[i-1]){continue}path.push(nums[i])回溯（i+1，sortNums）path.pop（）}}回溯（0，sortNums)returnresult};
