题目:
难度:Middle
相关话题:数组
、回溯算法
找出所有相加之和为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]]
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
let validNum=[]
let res=[]
let cache={}
function getSumComb(sum,validNum,times,start){
if(times===0){
if(sum===0)res.push(validNum.slice())
return
}
for(let i=start;i<=9;i++){
validNum.push(i)
getSumComb(sum-i,validNum,times-1,i+1)
validNum.pop()
}
}
getSumComb(n,validNum,k,1)
return res
};