题解 | #加起来和为目标值的组合(三)#

dfs, 退出条件为 总数超过 k 或者总和超过 n

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param k int整型 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def combination(self , k: int, n: int) -> List[List[int]]:
        # write code here
        res = []
        def dfs(s, t):
            nonlocal res
            if sum(t) > n or len(t) > k:
                return
            if sum(t) == n and  len(t) == k:
                res.append(list(t))
                return
            for i in range(s, 10):
                dfs(i + 1, t + [i])
        dfs(1, [])
        return res