原文：216. 组合总和 III(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0216/

题目：

难度：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
};