216. 组合总和 III

还是套模板，模板可参考：https://www.cnblogs.com/panweiwei/p/14025143.html

class Solution(object):
    def __init__(self):
        self.res = []

    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        nums = [i for i in range(1, 10)]
        sizeN = len(nums)
        self.dfs(nums, sizeN, k, n, 0, 0, [])
        return self.res

    def dfs(self, nums, sizeN, k, n, begin, temp_sum, temp):
        # 定义递归出口，长度为k且和为n
        if len(temp) == k and temp_sum == n:
            self.res.append(temp)
            return
        for i in range(begin, sizeN):
            if temp_sum > n or len(temp) > k:
                break
            self.dfs(nums, sizeN, k, n, i+1, temp_sum+nums[i], temp+[nums[i]])