代码编织梦想



题目

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

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
在这里插入图片描述
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思考

  • 1、和leetcode 77 组合题基本一致,就是我们循环递归的个数现在不是n来控制,而是就是9个嵌套
  • 2、题目要求我们需要总和,那么我们在递归函数中就需要定义一个sum,因为我们每次的值是不一样
  • 3、我们在回溯中不仅要将上一个元素弹出,去匹配另外一个树枝,并且需要重新计算sum值

代码和注释

class Solution {
    // 收集路径
    LinkedList<Integer> path = new LinkedList<>();
    // 结果集
    List<List<Integer>> result = new ArrayList<>();

    /**
        使用回溯法
        1、函数的参数
        2、终止条件按
        3、每轮递归干的事
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtacking(k, n, 0, 1);
        return result;
    }

    // 回溯函数 sum 是已经收集的总和
    public void backtacking(int k, int n,int sum, int startIdx){
        // 1、结束条件
        if(path.size() == k){
            // 当前和与目标和一致的时候需要收集结果
            if(sum == n){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        // 2、每轮递归回溯要干的事(剪枝)
        for(int i = startIdx; i <= 9-(k - path.size()) + 1; i++){
            sum +=i;
            path.add(i);
            // 开始的下标向后走
            backtacking(k, n, sum, i + 1);
            // 回溯
            path.removeLast();
            sum -= i;
        }
    }
}

总结

  • 1、回溯递归三部曲
    • a:定义递归函数的参数
    • b:终止条件【大多数为path集合深度和目标长度一致返回,加一个目标结果收集】
    • c:每轮递归要干嘛【业务+最后回溯】
  • 2、优化剪枝:总长-(目标长度-收集的长度)【其实这里我们考虑的就是至多递归到的位置,然后我们收集的长度有没有到目标长度】
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46643875/article/details/127998338

leetcode 216. 组合总和 iii_达达达达锅的博客-爱代码爱编程

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。解集不能包含重复的组合。  示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,

LeetCode 216. 组合总和 III-爱代码爱编程

和77. 组合差不多,区别在于这题目是求k个数之和=n,并且不存在重复的数字。 思路:回溯三部曲: 定义两个全局变量,result存放结果集,path存放如何条件的结果。 startIndex 记录下一层递归搜索的起始位置。终止条件:当到达叶子节点,即pathTop == k时,result收集path,return。单层搜索过程。处理节点、递归函数

Leetcode-216. 组合总和 III-爱代码爱编程

链接 216. 组合总和 III 题目 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 +

leetcode216. 组合总和 III-爱代码爱编程

1.题目描述: 找出所有相加之和为n的k个数的组合。组合中只允许含有1-9的正整数,并且每种组合中不存在重复的数字。说明:所有数字都是正整数;解集不能包含重复的组合。 2.回溯: 解法与图解leetcode77. 组合几乎一样。 class Solution { private List<List<Integer>&g

LeetCode216. 组合总和 III-爱代码爱编程

思路 根据回溯的模板就很容易想到了。 代码 class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); int sum

leetcode 216.组合总和iii_独影月下酌酒的博客-爱代码爱编程

1.题目描述 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示

leetcode 组合总和_bugmaker-shen的博客-爱代码爱编程

文章目录 39 组合总和40 组合总和II216 组合总和 III 39 组合总和 当前sum大于target时,就停止进入解空间树下一层 class Solution { public:

刷题看力扣,刷了两个月 leetcode 算法,顺利拿下百度、阿里等大厂的 offer_java程序v的博客-爱代码爱编程

随着互联网寒潮的到来, 越来越多的互联网公司提高了面试的难度,其中之一就是加大了面试当中手撕算法题的比例。这里说的算法题不是深度学习,机器学习这类的算法,而是排序,广度优先,动态规划这类既考核数据结构也考核编程能力的题目。刷题的网址非常的多,其中以 leetcode 是最为出名的。 在刷题上,我花了大量的时间,蹚了许多的坑,总结了一下,主要有这三个问题:

代码随想录算法训练营第四十四天| leetcode518. 零钱兑换 ii、leetcode377. 组合总和 Ⅳ_喵的博客-爱代码爱编程

一、LeetCode518. 零钱兑换 II         1:题目描述(518. 零钱兑换 II)         给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。         请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。         假设每一种面额的

leetcode 刷题 log day 44_音音子-的博客-爱代码爱编程

【完全背包问题】完全背包问题是指不限制物品的数量,可以无限制取物品。而 01 背包问题是每个物品只能取一次。 【求放满背包共有几种方法】: 递推公式:一般都是 dp[j] += dp[j - weight[i]];遍历顺序

【leetcode】1823. find the winner of the circular game(配数学证明)_记录算法题解的博客-爱代码爱编程

题目地址: https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/ 给定

【leetcode】1824. minimum sideway jumps_记录算法题解的博客-爱代码爱编程

题目地址: https://leetcode.com/problems/minimum-sideway-jumps/description/ 给定一条宽为

leetcode hot 100 —— 23.合并k个升序链表_hdu-五七小卡的博客-爱代码爱编程

题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 思路 在做本题之前,先考虑一下,如何合并两个有序链表,见 21.合并两个有序链表 最直接的思路就是,用一

算法学习 | 深度优先搜索~一条道走到黑_li_yizya的博客-爱代码爱编程

目录 员工的重要性 图像渲染  岛屿的周长  被围绕的区域 岛屿数量    深度优先搜索(Depth First Search):深度优先搜索属于图算法的一种,其过程主要是对每一个可能的分支路径深入到不能再深入到为止,而且每个节点只能访问一次。深度优先搜索本质上就是暴力搜索,遍历了所有可能的情况,必然能得到解。DFS搜索的流程是一

【leetcode】882. 细分图中的可到达节点_schanappi的博客-爱代码爱编程

题目描述 给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。 图用由边组成的二维数组 edges 表示,其中 edg

【栈和队列刷题】 有效的括号、删除字符串中的所有相邻重复项、用栈实现队列、用队列实现栈_繁华的梦境的博客-爱代码爱编程

LeetCode20. 有效的括号 来源:力扣(LeetCode) 链接:link 思路:使用一个栈,遍历字符串。如果栈为空就直接将字符加入。如果不为空,判断字符是左字符还是右字符。如果是左字符,直接加入;如果是右字符,判

leetcode337打家劫舍3刷题打卡_水番茄的博客-爱代码爱编程

337. 打家劫舍 III - 力扣(Leetcode) 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明

leetcode栈和队列练习-爱代码爱编程

文章目录 前言1.力扣20. 有效的括号1.题目分析 2.代码示现2.力扣225. 用队列实现栈1.题目分析2.代码实现 3.力扣232. 用栈实现队列1.题目分析2.代码实现 4.力扣622