前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >子集问题也要去重了!

子集问题也要去重了!

作者头像
代码随想录
发布2021-10-19 15:42:04
3630
发布2021-10-19 15:42:04
举报
文章被收录于专栏:代码随想录代码随想录

子集问题+去重

90.子集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] 来举例,如图所示:(注意去重需要先对集合排序

90.子集II

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

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

C++代码如下:

代码语言:javascript
复制
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去重的版本。

代码语言:javascript
复制
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。

代码如下:

代码语言:javascript
复制
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。

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

代码语言:javascript
复制
if (i > startIndex && nums[i] == nums[i - 1] ) {
        continue;
}

其他语言版本

Java

代码语言:javascript
复制
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

代码语言:javascript
复制
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

代码语言:javascript
复制
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

代码语言: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
};

旧文链接:回溯算法:求子集问题(二)

-------------end------------

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-10-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 代码随想录 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 90.子集II
  • 思路
  • 补充
  • 总结
  • 其他语言版本
    • Java
      • Python
        • Go
          • Javascript
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档