# Leetcode 216. Combination Sum III

## 題解

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        pos = [i for i in range(1,10)]
        output = []
        def dfs(start: int, sum: int, ans: List[int]):
            if sum > n:
                return
            if sum == n and len(ans) == k:
                output.append(ans[:])
            for i in range(start,9):
                num = pos[i]
                ans.append(num)
                dfs(i + 1,sum + num,ans)
                ans.pop()
        dfs(0,0,[])
        return output