问题216:找出所有相加之和为n
的k
个数的组合。组合中只允许含有1 - 9
的正整数,并且每种组合中不存在重复的数字。
这题就是两个限制条件,k
和n
,都满足就行。还是使用回溯法。
完整代码:
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtracking(cur, start, t):
if len(cur) == k and t == 0:
ans.append(cur)
return None
elif len(cur) == k:
return None
for i in range(start, 10):
if t-i < 0:
break
backtracking(cur+[i], i+1, t-i)
ans = []
backtracking([], 1, n)
return ans