# 216. Combination Sum III
#### Difficulty: Medium
link: https://leetcode.com/problems/combination-sum-iii/

### 1. Backtracking
#### $O(C^{9}_{k})$ runtime, $O(C^{9}_{k})$ space

用Backtracking檢查所有可能的組合，看看哪些符合條件，紀錄在result裡。

path紀錄了選過的數字，start_num代表要從哪個數字開始往後看，選擇下一個要加入的數字，value則代表n-sum(path)。

##### python

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        def backtracking(path, start_num, value):
            if value == 0 and len(path) == k:
                result.append(path)
                return
            for i in range(start_num, 10):
                if i > value or len(path) >= k:
                    break
                else:
                    backtracking(path + [i], i + 1, value - i)
        
        backtracking([], 1, n)
        return result

###### tags: `leetcode`