欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 216 组合总数(3)

程序员文章站 2024-02-24 11:37:52
...

题目

找出所有相加之和为 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,4]]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        def com(i, tmp_sum, tmp_arr):
            if tmp_sum == n and len(tmp_arr) == k:
                res.append(tmp_arr)
            if tmp_sum > n or len(tmp_arr) > k or i > 9:
                return 
            for j in range(i, 10):
                com(j + 1, tmp_sum + j, tmp_arr + [j])
        com(1, 0, [])
        return res

 

相关标签: 回溯