题目
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
1.只使用数字1到9
2.每个数字 最多使用一次
3.返回所有可能的有效组合的列表，该列表不能包含相同的组合两次，组合可以以任何顺序返回。
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
题解
第一种
我们先声明了一个数组res用于存储所有符合要求的组合，在声明一个sum变量用于记录当前组合的数字之和，在函数中声明了一个名为dfs的递归函数，该函数接收两个参数，分别是path和index，path数组用于记录当前组合中已经选择的数字，index参数用于表示从哪个数字开始搜索，在dfs函数中，我们先判断当前数字之和是否已经超过了n，如果是我们则直接返回，然后我们判断已经选择的数字数量是否等于k且数字之和等于n，如果是我们则将当前组合存入res数组中，然后我们使用循环从index开始遍历数字1-9，对于每个数字我们将其加入path数组中后在更新sum变量，并且去递归调用dfs函数，我们在将index参数更新为当前数字加1，当递归结束后，我们将当前数字从path数组中删除，然后再将sum变量减去当前数字，最后我们调用dfs函数并返回res数组即可
var combinationSum3 = function(k, n) { let res=[] let sum=0 const dfs=(path,index)=>{ if(sum>n){ return } if(path.length==k&&sum==n){ res.push(path.slice()) return } for(let i=index;i<=9;i++){ path.push(i) sum+=i dfs(path,i+1) sum-=i path.pop() } } dfs([],1) return res };
第二种
我们在函数中先声明了一个空数组ans，用于存储所有符合条件的组合，然后在声明了一个数组num，其中包含了从1到9的所有数字，然后我们使用循环，遍历num数组中的每一个数字，将其作为组合的第一个数字，然后我们调用一个名为help的递归函数，主要用于寻找符合条件的组合，help函数中我们接受几个参数，这也参数分别是num数组、组合中已经选取的数字个数count、当前已经选取的数字的和sum、已经选取的数字组成的数组temp、需要选取的数字个数k和目标数字和n，然后再进行判断是否选取的数字个数已经超过了k或者当前已经选取数字的和超过了n或者剩余可选数字的个数不足以组成剩余的数字个数，这样我们直接返回，如果已经选取的数字个数等于k，且当前已经选取的数字和等于n，我们就将当前组合存入ans数组中，然后我们使用循环，遍历剩余可选数字中的每一个数字，将其加入组合中后递归调用help函数，继续寻找符合条件的组合，最后返回出去即可
var combinationSum3 = function(k, n) { var ans=[] var num=[1,2,3,4,5,6,7,8,9] for(let i=0;i<9;i++){ help(num.slice(i+1),1,num[i],[num[i]],k,n) } function help(num,count,sum,temp,k,n){ if(count>k||sum>n||num.length<k-count){ return } if(sum===n&&count===k){ ans.push(temp) } for(let i=0;i<num.length;i++){ help(num.slice(i+1),count+1,sum+num[i],[...temp,num[i]],k,n) } } return ans };
