你知道吗？子集问题也要去重了！

子集问题+去重

创新互联专业为企业提供昔阳网站建设、昔阳做网站、昔阳网站设计、昔阳网站制作等企业网站建设、网页设计与制作、昔阳企业网站模板建站服务，10多年昔阳做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

子集II

力扣题目链接：https://leetcode-cn.com/problems/subsets-ii/

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集(幂集)。

说明：解集不能包含重复的子集。

示例:

  • 输入: [1,2,2]
  • 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

思路

做本题之前一定要先做78.子集。

这道题目和78.子集区别就是集合里有重复元素了，而且求取的子集要去重。

那么关于回溯算法中的去重问题，在40.组合总和II中已经详细讲解过了，和本题是一个套路。

剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。

用示例中的[1, 2, 2] 来举例，如图所示：(注意去重需要先对集合排序)

子集II

从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集!

本题就是其实就是78.子集的基础上加上了去重，去重我们在40.组合总和II也讲过了，所以我就直接给出代码了：

C++代码如下：

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking(vector& nums, int startIndex, vector& used) { 
    6.   
  
  
  
  6.         result.push_back(path); 
    7.   
  
  
  
  7.         for (int i = startIndex; i < nums.size(); i++) { 
    8.   
  
  
  
  8.             // used[i - 1] == true，说明同一树支candidates[i - 1]使用过 
    9.   
  
  
  
  9.             // used[i - 1] == false，说明同一树层candidates[i - 1]使用过 
    10.   
  
  
  
  10.             // 而我们要对同一树层使用过的元素进行跳过 
    11.   
  
  
  
  11.             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    12.   
  
  
  
  12.                 continue; 
    13.   
  
  
  
  13.             } 
    14.   
  
  
  
  14.             path.push_back(nums[i]); 
    15.   
  
  
  
  15.             used[i] = true; 
    16.   
  
  
  
  16.             backtracking(nums, i + 1, used); 
    17.   
  
  
  
  17.             used[i] = false; 
    18.   
  
  
  
  18.             path.pop_back(); 
    19.   
  
  
  
  19.         } 
    20.   
  
  
  
  20.     } 
    21.   
  
  
  
  21.  
    22.   
  
  
  
  22. public: 
    23.   
  
  
  
  23.     vector> subsetsWithDup(vector& nums) { 
    24.   
  
  
  
  24.         result.clear(); 
    25.   
  
  
  
  25.         path.clear(); 
    26.   
  
  
  
  26.         vector used(nums.size(), false); 
    27.   
  
  
  
  27.         sort(nums.begin(), nums.end()); // 去重需要排序 
    28.   
  
  
  
  28.         backtracking(nums, 0, used); 
    29.   
  
  
  
  29.         return result; 
    30.   
  
  
  
  30.     } 
    31.   
  
  
  
  31. }; 
    32.

使用set去重的版本。

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking(vector& nums, int startIndex, vector& used) { 
    6.   
  
  
  
  6.         result.push_back(path); 
    7.   
  
  
  
  7.         unordered_set uset; 
    8.   
  
  
  
  8.         for (int i = startIndex; i < nums.size(); i++) { 
    9.   
  
  
  
  9.             if (uset.find(nums[i]) != uset.end()) { 
    10.   
  
  
  
  10.                 continue; 
    11.   
  
  
  
  11.             } 
    12.   
  
  
  
  12.             uset.insert(nums[i]); 
    13.   
  
  
  
  13.             path.push_back(nums[i]); 
    14.   
  
  
  
  14.             backtracking(nums, i + 1, used); 
    15.   
  
  
  
  15.             path.pop_back(); 
    16.   
  
  
  
  16.         } 
    17.   
  
  
  
  17.     } 
    18.   
  
  
  
  18.  
    19.   
  
  
  
  19. public: 
    20.   
  
  
  
  20.     vector> subsetsWithDup(vector& nums) { 
    21.   
  
  
  
  21.         result.clear(); 
    22.   
  
  
  
  22.         path.clear(); 
    23.   
  
  
  
  23.         vector used(nums.size(), false); 
    24.   
  
  
  
  24.         sort(nums.begin(), nums.end()); // 去重需要排序 
    25.   
  
  
  
  25.         backtracking(nums, 0, used); 
    26.   
  
  
  
  26.         return result; 
    27.   
  
  
  
  27.     } 
    28.   
  
  
  
  28. }; 
    29.

补充

本题也可以不适用used数组来去重，因为递归的时候下一个startIndex是i+1而不是0。

如果要是全排列的话，每次要从0开始遍历，为了跳过已入栈的元素，需要使用used。

代码如下：

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking(vector& nums, int startIndex) { 
    6.   
  
  
  
  6.         result.push_back(path); 
    7.   
  
  
  
  7.         for (int i = startIndex; i < nums.size(); i++) { 
    8.   
  
  
  
  8.             // 而我们要对同一树层使用过的元素进行跳过 
    9.   
  
  
  
  9.             if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex 
    10.   
  
  
  
  10.                 continue; 
    11.   
  
  
  
  11.             } 
    12.   
  
  
  
  12.             path.push_back(nums[i]); 
    13.   
  
  
  
  13.             backtracking(nums, i + 1); 
    14.   
  
  
  
  14.             path.pop_back(); 
    15.   
  
  
  
  15.         } 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.  
    18.   
  
  
  
  18. public: 
    19.   
  
  
  
  19.     vector> subsetsWithDup(vector& nums) { 
    20.   
  
  
  
  20.         result.clear(); 
    21.   
  
  
  
  21.         path.clear(); 
    22.   
  
  
  
  22.         sort(nums.begin(), nums.end()); // 去重需要排序 
    23.   
  
  
  
  23.         backtracking(nums, 0); 
    24.   
  
  
  
  24.         return result; 
    25.   
  
  
  
  25.     } 
    26.   
  
  
  
  26. }; 
    27.

总结

其实这道题目的知识点，我们之前都讲过了，如果之前讲过的子集问题和去重问题都掌握的好，这道题目应该分分钟AC。

当然本题去重的逻辑，也可以这么写

 
 
 
 
      
  
  
  
  1. if (i > startIndex && nums[i] == nums[i - 1] ) { 
    2.   
  
  
  
  2.         continue; 
    3.   
  
  
  
  3. } 
    4.

其他语言版本

Java

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2.    List> result = new ArrayList<>();// 存放符合条件结果的集合 
    3.   
  
  
  
  3.    LinkedList path = new LinkedList<>();// 用来存放符合条件结果 
    4.   
  
  
  
  4.    boolean[] used; 
    5.   
  
  
  
  5.     public List> subsetsWithDup(int[] nums) { 
    6.   
  
  
  
  6.         if (nums.length == 0){ 
    7.   
  
  
  
  7.             result.add(path); 
    8.   
  
  
  
  8.             return result; 
    9.   
  
  
  
  9.         } 
    10.   
  
  
  
  10.         Arrays.sort(nums); 
    11.   
  
  
  
  11.         used = new boolean[nums.length]; 
    12.   
  
  
  
  12.         subsetsWithDupHelper(nums, 0); 
    13.   
  
  
  
  13.         return result; 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16.     private void subsetsWithDupHelper(int[] nums, int startIndex){ 
    17.   
  
  
  
  17.         result.add(new ArrayList<>(path)); 
    18.   
  
  
  
  18.         if (startIndex >= nums.length){ 
    19.   
  
  
  
  19.             return; 
    20.   
  
  
  
  20.         } 
    21.   
  
  
  
  21.         for (int i = startIndex; i < nums.length; i++){ 
    22.   
  
  
  
  22.             if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){ 
    23.   
  
  
  
  23.                 continue; 
    24.   
  
  
  
  24.             } 
    25.   
  
  
  
  25.             path.add(nums[i]); 
    26.   
  
  
  
  26.             used[i] = true; 
    27.   
  
  
  
  27.             subsetsWithDupHelper(nums, i + 1); 
    28.   
  
  
  
  28.             path.removeLast(); 
    29.   
  
  
  
  29.             used[i] = false; 
    30.   
  
  
  
  30.         } 
    31.   
  
  
  
  31.     } 
    32.   
  
  
  
  32. } 
    33.

Python

 
 
 
 
      
  
  
  
  1. class Solution: 
    2.   
  
  
  
  2.     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: 
    3.   
  
  
  
  3.         res = []  #存放符合条件结果的集合 
    4.   
  
  
  
  4.         path = []  #用来存放符合条件结果 
    5.   
  
  
  
  5.         def backtrack(nums,startIndex): 
    6.   
  
  
  
  6.             res.append(path[:]) 
    7.   
  
  
  
  7.             for i in range(startIndex,len(nums)): 
    8.   
  
  
  
  8.                 if i > startIndex and nums[i] == nums[i - 1]:  #我们要对同一树层使用过的元素进行跳过 
    9.   
  
  
  
  9.                     continue 
    10.   
  
  
  
  10.                 path.append(nums[i]) 
    11.   
  
  
  
  11.                 backtrack(nums,i+1)  #递归 
    12.   
  
  
  
  12.                 path.pop()  #回溯 
    13.   
  
  
  
  13.         nums = sorted(nums)  #去重需要排序 
    14.   
  
  
  
  14.         backtrack(nums,0) 
    15.   
  
  
  
  15.         return res 
    16.

Go

 
 
 
 
      
  
  
  
  1. var res[][]int 
    2.   
  
  
  
  2. func subsetsWithDup(nums []int)[][]int { 
    3.   
  
  
  
  3.  res=make([][]int,0) 
    4.   
  
  
  
  4.   sort.Ints(nums) 
    5.   
  
  
  
  5.  dfs([]int{},nums,0) 
    6.   
  
  
  
  6.  return res 
    7.   
  
  
  
  7. } 
    8.   
  
  
  
  8. func dfs(temp, num []int, start int)  { 
    9.   
  
  
  
  9.  tmp:=make([]int,len(temp)) 
    10.   
  
  
  
  10.  copy(tmp,temp) 
    11.   
  
  
  
  11.  
    12.   
  
  
  
  12.  res=append(res,tmp) 
    13.   
  
  
  
  13.  for i:=start;i  
  
  
  
  14.   if i>start&&num[i]==num[i-1]{ 
    15.   
  
  
  
  15.    continue 
    16.   
  
  
  
  16.   } 
    17.   
  
  
  
  17.   temp=append(temp,num[i]) 
    18.   
  
  
  
  18.   dfs(temp,num,i+1) 
    19.   
  
  
  
  19.   temp=temp[:len(temp)-1] 
    20.   
  
  
  
  20.  } 
    21.   
  
  
  
  21. } 
    22.

Javascript

 
 
 
 
      
  
  
  
  1. var subsetsWithDup = function(nums) { 
    2.   
  
  
  
  2.     let result = [] 
    3.   
  
  
  
  3.     let path = [] 
    4.   
  
  
  
  4.     let sortNums = nums.sort((a, b) => { 
    5.   
  
  
  
  5.         return a - b 
    6.   
  
  
  
  6.     }) 
    7.   
  
  
  
  7.     function backtracing(startIndex, sortNums) { 
    8.   
  
  
  
  8.         result.push(path.slice(0)) 
    9.   
  
  
  
  9.         if(startIndex > nums.length - 1) { 
    10.   
  
  
  
  10.             return 
    11.   
  
  
  
  11.         } 
    12.   
  
  
  
  12.         for(let i = startIndex; i < nums.length; i++) { 
    13.   
  
  
  
  13.             if(i > startIndex && nums[i] === nums[i - 1]) { 
    14.   
  
  
  
  14.                 continue 
    15.   
  
  
  
  15.             } 
    16.   
  
  
  
  16.             path.push(nums[i]) 
    17.   
  
  
  
  17.             backtracing(i + 1, sortNums) 
    18.   
  
  
  
  18.             path.pop() 
    19.   
  
  
  
  19.         } 
    20.   
  
  
  
  20.     } 
    21.   
  
  
  
  21.     backtracing(0, sortNums) 
    22.   
  
  
  
  22.     return result 
    23.   
  
  
  
  23. }; 
    24.

文章标题：你知道吗？子集问题也要去重了！
本文地址：http://www.csdahua.cn/qtweb/news26/254176.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

Google知识

行业网站建设

广告吸塑字　　 　香港云服务器租用　　 　东方电机技改服务有限公司　　 　网站推广　　 　csruizhi.cn　　 　响应式网站建设公司　　 　免备案虚拟主机　　 　成都资质代办　　 　申请域名　　 　广汉锦华　　 　成都做网站　　 　小程序　　 　成都网站建设公司　　 　腾讯香港免备案空间　　 　成都关键词SEO优化　　 　成都网站建设　　 　成都网站制作　　 　成都app软件开发　　 　四川审计公司　　 　网站定制