【回溯算法】77. 组合

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

77. 组合

解题思路

  • 回溯结束条件 track长度等于k 然后收集当前的路径
  • 遍历所有的节点 然后选择当前节点 通过start参数控制遍历 避免产生重复的子集
  • 移除当前的选择
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrack(1,n,k);
        return res;
    }

    void backtrack(int start,int n,int k){
        if(k == track.size()){
            // 当前回溯结束  收集当前记录
            res.add(new LinkedList<>(track));
            return;
        }

        // 回溯算法标准框架
        for(int i = start; i <= n; i++){
            // 路径 选择当前节点
            track.addLast(i);
            // 通过start参数控制树枝的遍历  避免产生重复的子集
            backtrack(i + 1, n,k);
            track.removeLast();// 移除当前选择
        }
    }
}

文章来源地址https://www.toymoban.com/news/detail-702260.html

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

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

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

相关文章

  • 力扣日记1.21-【回溯算法篇】77. 组合

    日期:2023.1.21 参考:代码随想录、力扣 终于结束二叉树了!听说回溯篇也是个大头,不知道这一篇得持续多久了…… 题目描述 难度:中等 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n = 4, k = 2 输出:

    2024年01月22日
    浏览(59)
  • 【力扣】77. 组合 <回溯、回溯剪枝>

    给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。 示例 1: 输入:n = 4, k = 2 输出: 示例 2: 输入:n = 1, k = 1 输出: 提示: 1 = n = 20 1 = k = n 暴力思考:k 等于多少就是多少层循环。 回溯 回溯法解决的问题都可以抽象为树形结构

    2024年02月12日
    浏览(41)
  • 77. 组合(回溯)

    和上一道回溯的题思路大致相同: 从前往后依次遍历,之后拼接的数字为当前数字 cur 的之后的数字,直到 list 的长度等于 k ,将 list 加入到 ans 当中。 特别注意: if 和 else 的区分,否则 if 要及时 return 回溯的时候新的 cur 值应该是 i+1 而不是 cur+1 ans.add(new ArrayList(list)); 在

    2024年02月02日
    浏览(43)
  • leetcode216. 组合总和 III(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combination-sum-iii 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输

    2024年02月10日
    浏览(45)
  • LeetCode算法题解(回溯)|39. 组合总和、40. 组合总和 II、131. 分割回文串

    题目链接:39. 组合总和 题目描述: 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数

    2024年02月05日
    浏览(58)
  • 【Leetcode60天带刷】day27回溯算法——39. 组合总和,40.组合总和II,131.分割回文串

    ​ 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限制重复

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

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

    2024年02月11日
    浏览(42)
  • Leetcode77. 组合

    给定两个整数  n  和  k ,返回范围  [1, n]  中所有可能的  k  个数的组合。 你可以按  任何顺序  返回答案。 回溯+剪枝 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

    2024年02月10日
    浏览(57)
  • LeetCode-77-组合

    一:题目描述: 给定两个整数 n 和 k ,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 二:示例与提示 示例 1: 示例 2: 提示: 1 = n = 20 1 = k = n 三:思路 回溯+剪枝 对于这类组合问题,可以将题目所描述的数组通过组合去构建一个树形结构 横向拓

    2024年02月09日
    浏览(34)
  • leetcode77组合 剪枝条件详细解释

    题目:77. 组合 - 力扣(LeetCode) 题解:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路来自代码随想录: 带你学透回溯算法-组合问题(对应力扣题目:77.组合)| 回溯法精讲!_哔哩哔哩_bilibili带你学透回溯算法-组合问题的剪枝操作(对应力扣题目:77.组合)| 回溯

    2024年02月20日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包