1. 问题描述：
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 说明： 所有数字都是正整数。 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-iii
2. 思路分析：
① 分析题目可以知道题目的规模大概是确定的，组合的数字是1~9而且是不允许重复的，我们需要尝试出所有的可能性才可以找到所有相加之和为 n 的 k 个数的组合，很明显这个问题是可以使用递归来解决的，递归就是在不知道的情况下去搜索问题的所有方案，在搜索的过程中找到满足题目条件的结果，所以对于这道题目来是可以使用递归来进行解决的
② 这个是1-9而且是不允许重复的数字组合，有点类似于填写数独上的数字的问题，只是处理的细节不一样而已，对于这道题目来说，也是需要在for循环中进行递归（类似于数独），比如k = 3, n = 9,当我们尝试出第一个结果[1,2,6],发现往下递归的过程中都是不满足n = 9的，最后将会退回到第二层也就是退回到数字2的情况，这个时候我们需要尝试数字3-9的情况，也就是尝试当前这一层的平行状态，所以会得到[1,3,5]这个结果，所以这个是需要在for循环中进行递归求解的，结合数独的问题会更好理解
③ 由②可知我们需要在for循环中进行递归，所以我们只需要在方法中传入需要的各个参数即可，比如需要记录当前已经使用了多少个数字了，当前累加的和使多少，需要传入记录中间结果的一个列表，当前正在递归的数字是哪一个：下一次递归的是当前数字的下一个数字这样才可以避免不重复使用数字的问题
记录中间结果的列表：我们需要往下递归之前进行剪枝，判断递归下去是否有意义，假如有意义那么需要在递归之前将当前的使用的数字记录下来，最后我们需要在出口中判断出当前使用的数字与累加的和是否等于题目中要求的k与n的值，假如相等那么加入到结果集中，并且需要return
④ 因为是1~9这个数字而且要求是不重复的，所以数据的规模并不是特别大，使用递归是可以求解出来的
3. 代码如下：
from typing import List class Solution: """ :param count:当前使用了多少个数字 :param cur: 当前使用的数字的累加和 :param num: 当前使用的数字, 往下递归的时候传入当前数字的下一个数字 :param res: 最后需要返回的结果列表 :param rec: 记录使用的数字中间结果 :return: """ def dfs(self, k: int, n: int, count: int, cur: int, num: int, res: List[List[int]], rec: List[int]): if count == k and cur == n: new = list() # 满足题目要求之后将结果加入到结果列表中 for i in range(k): new.append(rec[i]) res.append(new) # 退回到上一层 return for i in range(num, 10): # 剪枝: 只有当前使用的数字小于了k并且累加和使小于等于n的才进行递归 if count < k and cur + i <= n: # 添加当前的数字 rec.append(i) # i + 1表示递归当前数字的下一个数字这样可以避免重复 self.dfs(k, n, count + 1, cur + i, i + 1, res, rec) # 回溯: 弹出列表中加入的上一个元素, 尝试for循环中的下一个数字 rec.pop() def combinationSum3(self, k: int, n: int) -> List[List[int]]: res, rec = list(), list() # 使用dfs搜索即可 self.dfs(k, n, 0, 0, 1, res, rec) return res
