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