216. 组合总和 III(Medium)

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

样例

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

题目解析

本题就是在 77. 组合(Medium) 的基础上，加了约束条件的

约束条件：

len(tmp) == k and sum(tmp) == n

Python示例

def backtracking(k, n, ans, cur, tmp):
    if sum(tmp) > n: # 剪枝操作
        return 
    
    if len(tmp) == k and sum(tmp) == n:
        ans.append(tmp[:])
        return 
    for i in range(cur, 9 + 1):
        tmp.append(i)
        backtracking(k, n, ans, i + 1, tmp)
        tmp.pop()
    
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        backtracking(k, n, ans, 1, [])
        return ans