216. Combination Sum III

这道题目在微软现场面中遇到了，当年太傻没做出来，其实思路很简单，就是回溯，但是要注意回溯的树的树杈越来越少，代码如下：

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if k > 9*n:
            return []
        if k==0 and n != 0:
            return []
        if k < 0:
            return []
        res = []
        temp = []
        self.hs(k, n, temp, res, 1)
        return res
    def hs(self, j, n, temp, res, m):
        if j == 0 and n == 0:
            res.append(temp)
            return
        if j == 0:
            return
        if n <= 0:
            return
        for i in range(m, 10):
            self.hs(j-1, n-i, temp+[i], res, i+1)