首页 > 其他分享 >【每日一题】组合总和 III

【每日一题】组合总和 III

时间:2024-04-22 20:14:04浏览次数:19  
标签:target 组合 示例 int res path III 总和

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

和上一道题大同小异,不过这里是1~9的candidate数组,以及不能重复,每个组合的数字个数是给定的。

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        if k > n:
            return res

        def getComb(start, target, path):
            if target == 0 and len(path) == k:
                res.append(path[:])
                return
            for i in range(start, 10):
                if i > target: # 当前值大于target,直接跳出
                    break
                path.append(i) # 当前值加入组合列表
                getComb(i+1, target-i, path) # 从后一个值开始寻找结果
                path.pop()
        
        getComb(1, n, [])
        return res

 

标签:target,组合,示例,int,res,path,III,总和
From: https://www.cnblogs.com/Aikoin/p/18151398

相关文章

  • 组合模式
     1.组合模式介绍在解决组织结构这种具有层级关系的结构中,如果使用传统的继承,不能很好的实现管理的操作,比如学院,系的添加,删除,遍历等;所有可以使用组合模式把它们都看成组织结构,没有继承关系,而是一个树形结构。 2.实现publicabstractclassOrgComponent......
  • 组合恒等式
    最基础的就不说了1\[\sum_{i=0}^n(C_n^i)^2=C_{2n}^n\]证明:\(\sum_{i=0}^n(C_n^i)^2=\sum_{i=0}^nC_n^i\cdotC_n^i=\sum_{i=0}^nC_n^i\cdotC_n^{n-i}=C_{2n}^n\)2\[\sum_{i=0}^n(-1)^iC_n^i=[n=0]\]证明:由二项式定理,\(((-1)+1)^n=\sum_{i=0}^nC_n^i\cdot1^{n-i}\c......
  • 重复组合理论与公式
    从n个球当中,取出k个球,k个球允许重复出现,问有几种可能。解答:假设现在有编号的n个球,每一个编号的球有个,那么会有等式:,现在问题就转化为该等式一共有多少解?这里使用间隔法,即使用(n-1)个分隔符分隔得到n个空间,使得每一个空间之和为k.假设这里一共有5个球,取3次,那么需要4个分隔符去......
  • 洛谷题单指南-数学基础问题-P2651 添加括号III
    原题链接:https://www.luogu.com.cn/problem/P2651题意解读:计算能否在除法a1​/a2​/a3​/.../an​式子中加括号,将一部分数变成分子,使得除法结果是整数。解题思路:在a1​/a2​/a3​/.../an​中,无论怎么加括号,a1一定是分子,a2一定是分母,那么可以判断把a3...an都作为分子,是否能除尽......
  • 377. 组合总和 IV
    题目链接:本题是爬楼梯的又一变式。分析样例可知,每次选择的都可以是\(\rmnums\)中的任一个数,而最后选择完毕的数之和等于\(\rmtarget\).可以认为我们每次从\(\rmnums\)中选一个数作为往上爬的台阶数,问爬\(\rmtarget\)个台阶有多少种方案。因此爬楼梯那个题可以认为......
  • 06、Underlay网络和Overlay网络的组合
    Underlay网络和Overlay网络的组合建立VXLAN隧道的基础网络称为Underlay网络,VXLAN隧道所承载的业务网络称为Overlay网络,因此在VXLAN场景中存在以下几种Underlay网络和Overlay网络的组合:类别解释示例IPv4overIPv4Overlay网络和Underlay网络均为IPv4网络。......
  • 27天【代码随想录算法训练营34期】第七章 回溯算法part03(● 39. 组合总和 ● 40.组合
    39.组合总和怎么才能避免重复?比现在数小的数就别append到path里面了,之前肯定都试过了classSolution:defcombinationSum(self,candidates:List[int],target:int)->List[List[int]]:result=[]candidates.sort()self.backtracking(cand......
  • 25天【代码随想录算法训练营34期】第七章 回溯算法part02 ( ● 216.组合总和III ● 17
    **216.组合总和III**classSolution:defcombinationSum3(self,k:int,n:int)->List[List[int]]:result=[]self.backtracking(k,n,1,[],result,n)returnresultdefbacktracking(self,k,n,startingIndex,path,result,......
  • 24天【代码随想录算法训练营34期】第七章 回溯算法part01 ( ● 理论基础 ● 77. 组合
    **理论基础**voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){处理节点;backtracking(路径,选择列表);//递归回溯,撤销处理结果}}......
  • P1157 组合的输出
    P1157组合的输出题目排列与组合是常用的数学方法,其中组合就是从\(n\)个元素中抽出\(r\)个元素(不分顺序且\(r\len\)),我们可以简单地将\(n\)个元素理解为自然数\(1,2,\ldots,n\),从中任取\(r\)个数。现要求你输出所有组合。例如\(n=5,r=3\),所有组合为:\(123,124,125......