题目
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.
解题思路
回溯，递归的时候需要当前可以放的数，还需要放的数的个数，距离目标还差几，以及临时的结果
代码
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def dfs(cur, k, n, tmp):
if k == 0:
if n == 0:
res.append(tmp[:])
return
for i in range(cur, 10):
if i > n:
return
tmp.append(i)
dfs(i + 1, k - 1, n - i, tmp)
tmp.pop()
res = []
dfs(1, k, n, [])
return res
