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

子集问题+去重

子集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++代码如下：

class Solution {  private:     vector<vector<int>> result;     vector<int> path;     void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {          result.push_back(path);         for (int i = startIndex; i < nums.size(); i++) {              // used[i - 1] == true，说明同一树支candidates[i - 1]使用过             // used[i - 1] == false，说明同一树层candidates[i - 1]使用过             // 而我们要对同一树层使用过的元素进行跳过             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {                  continue;             }             path.push_back(nums[i]);             used[i] = true;             backtracking(nums, i + 1, used);             used[i] = false;             path.pop_back();         }     } public:     vector<vector<int>> subsetsWithDup(vector<int>& nums) {          result.clear();         path.clear();         vector<bool> used(nums.size(), false);         sort(nums.begin(), nums.end()); // 去重需要排序         backtracking(nums, 0, used);         return result;     } }; 

使用set去重的版本。

class Solution {  private:     vector<vector<int>> result;     vector<int> path;     void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {          result.push_back(path);         unordered_set<int> uset;         for (int i = startIndex; i < nums.size(); i++) {              if (uset.find(nums[i]) != uset.end()) {                  continue;             }             uset.insert(nums[i]);             path.push_back(nums[i]);             backtracking(nums, i + 1, used);             path.pop_back();         }     } public:     vector<vector<int>> subsetsWithDup(vector<int>& nums) {          result.clear();         path.clear();         vector<bool> used(nums.size(), false);         sort(nums.begin(), nums.end()); // 去重需要排序         backtracking(nums, 0, used);         return result;     } }; 

补充

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

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

代码如下：

class Solution {  private:     vector<vector<int>> result;     vector<int> path;     void backtracking(vector<int>& nums, int startIndex) {          result.push_back(path);         for (int i = startIndex; i < nums.size(); i++) {              // 而我们要对同一树层使用过的元素进行跳过             if (i > startIndex && nums[i] == nums[i - 1] ) {  // 注意这里使用i > startIndex                 continue;             }             path.push_back(nums[i]);             backtracking(nums, i + 1);             path.pop_back();         }     } public:     vector<vector<int>> subsetsWithDup(vector<int>& nums) {          result.clear();         path.clear();         sort(nums.begin(), nums.end()); // 去重需要排序         backtracking(nums, 0);         return result;     } }; 

总结

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

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

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

其他语言版本

Java

class Solution {     List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果    boolean[] used;     public List<List<Integer>> subsetsWithDup(int[] nums) {          if (nums.length == 0){              result.add(path);             return result;         }         Arrays.sort(nums);         used = new boolean[nums.length];         subsetsWithDupHelper(nums, 0);         return result;     }     private void subsetsWithDupHelper(int[] nums, int startIndex){          result.add(new ArrayList<>(path));         if (startIndex >= nums.length){              return;         }         for (int i = startIndex; i < nums.length; i++){              if (i > 0 && 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;         }     } } 

Python

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

Go

var res[][]int func subsetsWithDup(nums []int)[][]int {   res=make([][]int,0)   sort.Ints(nums)  dfs([]int{ },nums,0)  return res } func dfs(temp, num []int, start int)  {   tmp:=make([]int,len(temp))  copy(tmp,temp)  res=append(res,tmp)  for i:=start;i<len(num);i++{    if i>start&&num[i]==num[i-1]{     continue   }   temp=append(temp,num[i])   dfs(temp,num,i+1)   temp=temp[:len(temp)-1]  } } 

Javascript

var subsetsWithDup = function(nums) {      let result = []     let path = []     let sortNums = nums.sort((a, b) => {          return a - b     })     function backtracing(startIndex, sortNums) {          result.push(path.slice(0))         if(startIndex > nums.length - 1) {              return         }         for(let i = startIndex; i < nums.length; i++) {              if(i > startIndex && nums[i] === nums[i - 1]) {                  continue             }             path.push(nums[i])             backtracing(i + 1, sortNums)             path.pop()         }     }     backtracing(0, sortNums)     return result }; 源码下载

很赞哦!（16）