难度: Medium
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 91 <= n <= 60运行时间: 32 ms
内存: 14.8 MB
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
candidates = list(range(1, 10))
result = []
def backtrack(path, start):
s = sum(path)
if len(path) == k and s == n:
result.append(list(path))
if len(path) >= k:
return
if s >= n:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(path, i+1)
path.pop()
backtrack([], 0)
return result
这个题解使用了回溯算法。它首先定义了候选数字集合candidates为1到9。然后定义了一个辅助函数backtrack，用于生成所有可能的组合。在backtrack函数中，如果当前路径path的长度等于k且路径上数字的和等于n，则找到一个有效组合，将其加入结果列表result中。如果path长度已经大于等于k或者数字和已经大于等于n，则剪枝返回，因为继续搜索也不会找到有效组合。否则，从candidates中当前位置start开始，依次将每个数字加入path，递归调用backtrack，然后再将该数字从path中移除，实现回溯。最后，在主函数中调用backtrack，并返回结果列表result。
时间复杂度: O(9^k)
空间复杂度: O(k) + O(C(9,k))
```python
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
candidates = list(range(1, 10)) # 定义候选数字集合
result = [] # 存储结果的列表
def backtrack(path, start):
s = sum(path)
if len(path) == k and s == n: # 找到一个有效组合
result.append(list(path))
if len(path) >= k: # 剪枝：path长度超过k
return
if s >= n: # 剪枝：数字和超过n
return
for i in range(start, len(candidates)):
path.append(candidates[i]) # 选择当前数字
backtrack(path, i+1) # 递归调用
path.pop() # 回溯：移除当前数字
backtrack([], 0) # 调用回溯函数
return result
```
回溯算法是解决组合、排列和子集问题的常用方法，特别适用于需要探索所有可能解的情况。考虑到组合总和 III 需要找出所有可能的组合使其数字之和等于 n，且组合中数字个数为 k，这种问题的本质是寻找满足特定条件的所有子集，这正是回溯算法擅长的。虽然可以考虑使用动态规划，特别是在处理类似“组合总和”的问题时，但在这种需要明确组合中数字个数的情况下，动态规划的实现会相对复杂，不如回溯直观和简单。因此，考虑到问题的特性和实现的简洁性，使用回溯算法是最合适的选择。
在这个问题中，使用 path 列表的长度和数字总和控制递归终止是合理的。因为一旦 path 的长度超过了 k 或者数字总和超过了 n，继续添加更多的数字不会得到有效的解。所以这种剪枝方式并不会导致有效组合被过早地剪枝掉，反而是一种避免无效计算和提高算法效率的必要措施。
选择1到9作为候选数字集合是根据题目的要求。题目指定是找出所有可能的组合使其数字之和等于 n，且每个组合恰好包含 k 个不重复的数字，这些数字取自1到9。这个范围确保了每个数字都是独一无二的，且符合常见的数字组合逻辑，不需要处理较大数字或是负数的复杂情况。
在题解中，'每个节点最多有 n 个子节点'实际上是指，每个节点在递归过程中最多考虑从当前数字开始到9的数字作为可能的子节点。在实际的回溯树中，每次递归调用backtrack函数时，都会从 'start' 参数指定的位置开始尝试将每个数字加入到当前的 path 中，并递归地继续探索加入下一个数字的可能性。这里的 'n' 更多是代指候选数字的个数上限，而不是严格的子节点数。每次递归都会将 'start' 参数加一，这样就可以确保不会重复使用数字，符合题目“组合中的数字是不重复”的要求。