78 子集

这篇具有很好参考价值的文章主要介绍了78 子集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:
输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素互不相同

题解1 回溯

class Solution {
    vector<vector<int>> ret;
    deque<int> tmp;
public:
    void backtrace(vector<int>& nums, int len, int idx){
        if(len > nums.size()) return;
        if(tmp.size() == len){
            ret.push_back(vector<int>(tmp.begin(), tmp.end()));
            // idx 此时还没用过
            backtrace(nums, len+1, idx);
            return;
        }
        for(int i = idx; i < nums.size(); i++){
            tmp.push_back(nums[i]);
            backtrace(nums, len, i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrace(nums, 0, 0);
        return ret;
    }
};

78 子集,HOT100,回溯,mask,算法,leetcode,数据结构

模板

78 子集,HOT100,回溯,mask,算法,leetcode,数据结构

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
public:
    void backtrace(vector<int>& nums, int idx){
        if(idx == nums.size()){
            ret.push_back(tmp);
            return;
        }
        tmp.push_back(nums[idx]);
        // 选
        backtrace(nums, idx+1);
        tmp.pop_back();
        // 不选
        backtrace(nums, idx+1);

    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrace(nums, 0);
        return ret;
    }
};

78 子集,HOT100,回溯,mask,算法,leetcode,数据结构

题解2 迭代(mask思想)

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> tmp;
        int s = nums.size();
        // 每个子集对应一个长度为s的01序列,第i位表示nums[i]是否在子集中
        // mask 的值代表tmp当前有多少个元素,以及nums哪几个元素在tmp里
        for(int mask = 0; mask < 1 << s; mask ++){
            tmp.clear();

            for(int i = 0; i < s; i++)
            // 根据mask的值把元素放到tmp里
                if(mask & (1<<i)) 
                    tmp.push_back(nums[i]);
            
            ret.push_back(tmp);
        }
        return ret;
    }
};

78 子集,HOT100,回溯,mask,算法,leetcode,数据结构文章来源地址https://www.toymoban.com/news/detail-722034.html

到了这里,关于78 子集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】416、LeetCode分割等和子集

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题可以抽象成一个01背包的问题,关于01背包可以看【算法与数据结构】算法与数据结构知识点。 本题只需要求出数组的累积和,然后和的一半就可以视为背包的最大重量,目标

    2024年01月19日
    浏览(41)
  • 力扣hot100:416.分割等和子集(组合/动态规划/STL问题)

    组合数问题 我们思考一下,如果要把数组分割成两个子集,并且两个子集的元素和相等,是否等价于在数组中寻找若干个数使之和等于所有数的一半?是的! 因此我们可以想到,两种方式: ①回溯的方式找到target,但是回溯是阶乘级别的算法,这里会超时。 ②从前往后遍历

    2024年04月28日
    浏览(36)
  • Java算法_ 验证二叉搜索树(LeetCode_Hot100)

    题目描述: 给你一个二叉树的根节点 ,判断其是否是一个有效的二叉搜索树。root 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 获得更多?算法思路:代码文

    2024年02月12日
    浏览(39)
  • 代码随想录-回溯算法(子集问题)|ACM模式

    目录 前言: 78. 子集 题目描述: 输入输出描述: 思路和想法: 90. 子集 II 题目描述: 输入输出描述: 思路和想法: 491. 递增子序列 题目描述: 输入输出描述: 思路和想法: 如果把 子集问题、组合问题、分割问题都抽象为一棵树的话, 那么组合问题和分割问题都是收集

    2024年02月15日
    浏览(126)
  • 7-1 子集和问题--回溯法(算法设计与分析)

    作者 陈晓梅    单位 广东外语外贸大学 设集合S={x1,x2,…,xn}是一个正整数集合,c是一个正整数,子集和问题判定是否存在S的一个子集S1,使S1中的元素之和为c。试设计一个解子集和问题的回溯法,并输出利用回溯法在搜索树(按输入顺序建立)中找到的第一个解。 输入格

    2024年02月04日
    浏览(40)
  • 【LeetCode】HOT 100(16)

    精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。 目录 题单介绍: 题目:124. 二叉树中的最大路径和 - 力扣(Leetcode) 题目的接口: 解题思路:

    2024年02月12日
    浏览(33)
  • LeetCode 热题 HOT 100

    重点是当有一个链表为空了不单独处理,按节点为0处理。 滑动窗口! 首先要判断slow需不需要更新,怎么判断?slow = max(umap[s[fast]], slow);什么意思,就是说:**umap[s[fast]]的意义是,为了在slow和fast之间不出现重复字符,slow能处于的最左位置。**如图,当j第一次到d,将umap[s[j

    2024年02月07日
    浏览(46)
  • 【LeetCode】HOT 100(23)

    精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。 目录 题单介绍: 题目:448. 找到所有数组中消失的数字 - 力扣(Leetcode) 题目的接口: 解题思路

    2024年02月12日
    浏览(57)
  • 【LeetCode】HOT 100(18)

    精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。 目录 题单介绍: 题目:148. 排序链表 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过过过

    2024年02月15日
    浏览(39)
  • 【LeetCode】HOT 100(20)

    精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。 目录 题单介绍: 题目:621. 任务调度器 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过过

    2024年02月16日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包