代码编织梦想

题目

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

  • 只使用数字1到9 每个数字
  • 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例

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

解析

这道题和上一道组合问题很接近,只不过是多了一个终止条件,直接上回溯+剪枝的代码:

func combinationSum3(k int, n int) [][]int {
    //要找K个数的和为n
    var res [][]int
    var path []int
    sum := 0
    var backTrack func(int)
    backTrack = func(startIndex int) {
        //剪枝
        if sum > n || len(path) > k {
            return 
        }
        //递归终止条件
        if len(path) == k && sum == n {
            tmp := make([]int, k) //一样的原因
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        //单层递归循环+剪枝
        for i := startIndex; i <= 9-(k-len(path))+1; i++ {
            sum += i
            path = append(path, i)
            backTrack(i+1)
            //回溯
            sum -= i
            path = path[:len(path)-1]
        }
    }
    backTrack(1)
    return res
}

也可以将结果定义成函数外面的全局变量,然后在外定义函数;或者传数组的地址进来:

func combinationSum3(k int, n int) [][]int {
    //要找K个数的和为n
    var res [][]int
    var path []int
    var sum int
    backTrack(n, k, 1, sum, &path, &res)
    return res
}

func backTrack(n, k, startIndex, sum int, path *[]int, res *[][]int) {
    if sum > n || len(*path) > k {
        return
    }
    if sum == n && len(*path) == k {
        tmp := make([]int, k)
        copy(tmp, *path)
        *res = append(*res, tmp)
        return
    }
    for i := startIndex; i <= 9-(k-len(*path))+1; i++ {
        sum += i
        *path = append(*path, i)
        backTrack(n, k, i+1, sum, path, res)
        sum -= i
        *path = (*path)[:len(*path)-1]
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/midi666/article/details/128012650

leetcode_216 组合总和 iii_ding_xiaofei的博客-爱代码爱编程

题目描述 题解 基本就和77是一样的组合问题 import java.util.*; public class Leetcode_216 { public List<List<Integer&

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,

leetcode216组合总和iii_「已注销」的博客-爱代码爱编程_找出所有相加之和为 nn 的 kk 个数的组合。组合中只允许含有1-9的正整数,并且每种

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

LeetCode 216 组合总和III HERODING的LeetCode之路-爱代码爱编程

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

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,3,

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

class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { List<In

Leetcode216 组合总和III-爱代码爱编程

@Leetcode相对于组合问题,只是多了一个限制,即所求集合总和为n; 回溯三步曲 确定递归函数参数 void generateSum(int k, int n, int sum, int startIndex, vector &p) 确定终止条件if(p.size() == k){ if(sum == n) res

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

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/com

LeetCode 216 组合总和 III -- 回溯法-爱代码爱编程

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum-iii 题意: 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k

LeetCode_216 组合总和III-爱代码爱编程

1、题目:组合总和III 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次  返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 2、解题思路 思路非常类似于77题,在77基础上加上sum值来判断已经收集的值是否等于题目要求的和。 接下来就

leetcode 494.目标和 动态规划背包问题 (c++版本)_学不完了ccccc的博客-爱代码爱编程

题目描述 说白了就是让一部分数减去剩下的一部数使得差值为target,计算有多少中组合的方法 下面来个数学公式推导一下 l

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

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

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

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

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

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