【LeetCode-中等题】78. 子集

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

组合+并集问题汇总:

1、子集去重版本
2、组合非去重版本
3、组合去重版本

题目

【LeetCode-中等题】78. 子集,力扣,# 中等题,leetcode,算法,职场和发展
注意:这里的nums数组里面的元素是各不相同的,所以不存在去重操作

方法一:动态规划

【LeetCode-中等题】78. 子集,力扣,# 中等题,leetcode,算法,职场和发展
【LeetCode-中等题】78. 子集,力扣,# 中等题,leetcode,算法,职场和发展

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>>  res = new ArrayList<>();//结果集
        res.add(new ArrayList<>());// 首先将空集加入解集中
        int n =  nums.length;
        List<Integer> zres = null;
        for(int i = 0 ; i < n ; i++){
            int size = res.size(); // 当前子集数
            for(int j = 0 ; j<size ;j++){
                zres = new ArrayList<>(res.get(j));// 拷贝所有子集
                zres.add(nums[i]);// 向拷贝的子集中加入当前数形成新的子集
                res.add(zres);// 向lists中加入新子集
            }
        }
        return res;
    }

方法二:递归加回溯(关键----startIndex)

参考讲解视频:回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集

根据nums[1,2,3] 可以画出树图,收获的结果集为所有节点,并且根据startIndex 每次只能取startIndex 后面的数,这样可以避免取到【1,2】 【2,1】这样的集合 这两个集合其实是同一个子集,所以每次递归都让startIndex +1 让递归后的只能取startIndex 后面的数

并且注意回溯(在递归后删除递归前加入的数)
【LeetCode-中等题】78. 子集,力扣,# 中等题,leetcode,算法,职场和发展

【LeetCode-中等题】78. 子集,力扣,# 中等题,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-709109.html

    List<List<Integer>> res = new ArrayList<>();//结果集
    public List<List<Integer>> subsets(int[] nums) {
       List<Integer> zres  = new ArrayList<>();
        int  startIndax = 0;//每一次取子结果的开始位置,第一次肯定从第一个位置开始
       dfsback(nums,startIndax,zres);
       return res;
    }
    //递归+回溯
    public void  dfsback(int[]nums,int startIndax, List<Integer> zres){
            res.add(new ArrayList<>(zres));//收获结果
            if(startIndax >= nums.length) return ;//这个条件有没有都没关系  因为如果startIndax >= nums.length  那么下面的for循环根本不会执行  自然会return掉
            for(int i = startIndax ; i<nums.length  ;i++){
                zres.add(nums[i]);//收获子结果集
                dfsback(nums,i + 1 ,zres);//往下递归
                zres.remove(zres.size()-1);//回溯,还原状态
            }
    }

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

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

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

相关文章

  • 【贪心算法】Leetcode 55. 跳跃游戏【中等】

    给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1: 输入 :nums = [2,3,1,1,4] 输出: true 解释 :可以先跳 1 步,从下标

    2024年04月28日
    浏览(54)
  • 【算法与数据结构】416、LeetCode分割等和子集

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

    2024年01月19日
    浏览(43)
  • LeetCode_贪心算法_中等_763.划分字母区间

    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。 示例 1: 输入:s = “ababcbacadefegdehijhklij” 输出

    2024年02月14日
    浏览(84)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(45)
  • [Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读

    人不走空                                                                          目录         🌈个人主页:人不走空       💖系列专栏:算法专题 ⏰诗词歌赋:斯是陋室,惟吾德馨 题目 示例 示例1 示例2 示例3  提示  详细解读 作者其他作品:   给你一

    2024年02月19日
    浏览(36)
  • 力扣(LeetCode)算法_C++—— 快乐数

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是

    2024年02月09日
    浏览(40)
  • 算法学习——LeetCode力扣回溯篇2

    40. 组合总和 II - 力扣(LeetCode) 描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 示例 示例 1: 输入: candidates = [10,1,2,7

    2024年02月20日
    浏览(36)
  • 力扣(LeetCode)算法_C++—— 存在重复元素

    给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。 示例 1: 输入:nums = [1,2,3,1] 输出:true 示例 2: 输入:nums = [1,2,3,4] 输出:false 示例 3: 输入:nums = [1,1,1,3,3,4,3,2,4,2] 输出:true 提示: 1 = nums.length = 105 -1

    2024年02月09日
    浏览(46)
  • LeetCode面试算法-力扣 88. 合并两个有序数组

    88. 合并两个有序数组 题目描述     给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由函数返回,而是存储

    2024年02月10日
    浏览(49)
  • 算法学习——LeetCode力扣字符串篇

    344. 反转字符串 - 力扣(LeetCode) 描述 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 示例 1: 输入:s = [“h”,“e”,“l”

    2024年02月20日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包