## Description

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

• All numbers will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]


Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]


## Solutions

### 1. Backtracking

连续做了之前的两题，这里就只要注意下写死 10 就好了，因为不能是两位数。

# Time: O(n^size)
# Sapce: O(n)
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
self.dfs(k, 1, n, [], res)
return res

def dfs(self, size, start, target, path, res):
if target == 0 and len(path) == size:
res.append(path)

l = len(path)
for i in range(start, 10):
if target >= i and l <= size:
self.dfs(size, i + 1, target - i, path + [i], res)
# 18/18 cases passed (28 ms)
# Your runtime beats 96.4 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)