专栏首页代码随想录回溯算法:求子集问题(二)

回溯算法:求子集问题(二)

给「代码随想录」一个星标吧!

通知:我将公众号文章和学习相关的资料整理到了Github :https://github.com/youngyangyang04/leetcode-master,方便大家在电脑上学习,可以fork到自己仓库,顺便也给个star支持一波吧! ❞

第90题.子集II

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

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

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

示例: 输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

思路

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

这道题目和回溯算法:求子集问题!区别就是集合里有重复元素了,而且求取的子集要去重。

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

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

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

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

本题就是其实就是回溯算法:求子集问题!的基础上加上了去重,去重我们在回溯算法:求组合总和(三)也讲过了,所以我就直接给出代码了:

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;
    }
};

总结

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

「就酱,如果感觉融会贯通了,就把「代码随想录」介绍给自己的同学朋友吧,也许他们也需要!」

本文分享自微信公众号 - 代码随想录(code_thinking),作者:程序员Carl

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 回溯算法:求子集问题!

    题目地址:https://leetcode-cn.com/problems/subsets/

    代码随想录
  • 双指针法:一样的道理,能解决四数之和

    题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c ...

    代码随想录
  • 回溯算法:递增子序列

    题目链接:https://leetcode-cn.com/problems/increasing-subsequences/

    代码随想录
  • 回溯算法:求子集问题!

    题目地址:https://leetcode-cn.com/problems/subsets/

    代码随想录
  • 牛客练习赛23 D

      利用全排列函数加vector数组,开十个vector,存a到i字母出现的位置,最后每个vector再push_back(字符串长度加一)作为结束标志。

    用户2965768
  • 递归&回溯-子集之和

    Q:已知一个数组,可能有重复元素,给定值target,求出所有子集中,和为target的,不重复的子集。

    BUPTrenyi
  • 浅谈求子集问题

    又是一周过去了,大家这周有木有在算法上有所精进呢?今天我们来看看一些让我们求子集的问题,许多问题涉及到处理给定元素的排列组合,我们需要巧妙地处理它们。这类问题可...

    写代码的阿宗
  • 干货 | 十分钟掌握禁忌搜索算法求解带时间窗的车辆路径问题(附C++代码和详细代码注释)

    一 什么是禁忌搜索算法? 禁忌搜索算法(Tabu Search Algorithm,简称TS)起源于对于人类记忆功能的模仿,是一种亚启发式算法(meta-...

    用户1621951
  • 苹果患上iPhone依赖症

    新一代iPhone定价太高销量低迷,业界都猜测苹果是将会推出廉价产品,抑或像小米+红米一样采取双品牌战略(比如苹果+青苹果),库克直接否认了这种说法。

    罗超频道
  • zxing二维码生成服务之深度定制

    二维码生成服务之深度定制 之前写了一篇二维码服务定制的博文,现在则在之前的基础上,再进一步,花样的实现深度定制的需求,我们的目标是二维码上的一切都是可以由用户...

    一灰灰blog

扫码关注云+社区

领取腾讯云代金券