力扣日记1.22-【回溯算法篇】216. 组合总和 III

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

力扣日记:【回溯算法篇】216. 组合总和 III

日期:2023.1.22
参考:代码随想录、力扣

216. 组合总和 III

题目描述

难度:中等

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次
  • 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

题解

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    int sum = 0;    // 记录当前和
    // 树的宽度为集合长度(1~9),树的深度为k(最多递归k层)
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);  // 从1开始
        return result;
    }
    // 返回值为void,参数为k, n以及当前集合开始遍历的位置
    void backtracking(int k, int n, int startindex) {
        // 终止(判断)
        // 最多只能有k个数
        if (path.size() == k) {
            if (sum == n) {
                // 如果满足条件则添加进结果集
                result.push_back(path);
            }
            return;
        }
        // 未到达k, 则 for 循环遍历当前集合
        // 剪枝1:如果剩余可遍历的元素个数不足以构成组合则不需要再遍历(注意这里最大就是9,即组合问题的n=9)
        // path.size() + (9 - startindex + 1) >= k
        // 剪枝2:能在这里遍历说明组合path还未到达k个,但如果此时sum已经>=n,则越往后的sum肯定超过n,则不需要再遍历
        if (sum >= n) return;
        for (int i = startindex; i <= path.size() + 9 + 1 - k; i++) { 
            // 处理节点
            path.push_back(i);
            sum += i;
            // 递归
            backtracking(k, n, i + 1);
            // 回溯
            path.pop_back();
            sum -= i;
        }
        return;
    }
};

复杂度

时间复杂度:
空间复杂度:文章来源地址https://www.toymoban.com/news/detail-819168.html

思路总结

  • 思路与77.组合基本一致,只是多了一个“相加之和为n”的判断
  • 注意这道题,集合即为[1,2,…,9],即类比77.组合问题的n在本题中固定为9(注意与本题的n区别),即for循环遍历的最大个数为9。从这个集合中找k个值,使其和为n。
  • 剪枝可从两处进行,一是遍历剩余集合个数;二是sum>n的情况(这里我与代码随想录的区别是,代码随想录是在函数最开始(终止条件之前)就对sum进行判断(如果sum>n则return),我是在终止条件之后,即如果组合个数未达到k个,但是sum却>=n了(等于n也不行),则不满足需剪枝
  • sum也可以设置为backtracking的参数

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

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

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

相关文章

  • 代码随想录22| 216.组合总和III, 17.电话号码的字母组合

    题目链接/文章讲解:链接地址 视频讲解:链接地址 代码思路:回溯三部曲: 1.确定函数参数:n,k,sum,startIndex; 2.结束条件,path == k,并且如果sum==n 结束递归 3.递归回溯逻辑。 题目链接/文章讲解:链接地址 视频讲解:链接地址 代码思路:传入参数:输入的数字,第几个数字的

    2024年02月11日
    浏览(56)
  • 【LeetCode:216. 组合总和 III + 递归】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年04月25日
    浏览(59)
  • Leetcode—216.组合总和III【中等】

    之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

    2024年01月23日
    浏览(43)
  • 力扣日记1.21-【回溯算法篇】77. 组合

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

    2024年01月22日
    浏览(65)
  • 力扣第40题 组合总和 || c++ 回溯经典

    40. 组合总和 II 中等 相关标签 数组   回溯 给定一个候选人编号的集合  candidates  和一个目标数  target  ,找出  candidates  中所有可以使数字和为  target  的组合。 candidates  中的每个数字在每个组合中只能使用  一次  。 注意: 解集不能包含重复的组合。  示例 1: 示例

    2024年02月07日
    浏览(40)
  • DAY25:回溯算法组合题216、17

    经过了昨天组合的题目的学习,这道题比较简单,套用之前的模板就可以 基本思路 终止条件,遇到向量的个数一样,并且sum等于n的时候终止。 输入变量,n,k,还有起始的idx和基于当前元素之和的sum 逻辑就是,按照循环递归下去,注意要对sum值进行回溯。 时间复杂度O(n *

    2024年01月20日
    浏览(37)
  • 每日OJ题_DFS回溯剪枝⑨_力扣39. 组合总和(两种思路)

    目录 力扣39. 组合总和 解析代码1 解析代码2 39. 组合总和 LCR 081. 组合总和 难度 中等 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序

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

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

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

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

    2024年02月11日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包