慕运维5049730
**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
const combinationSum3 = (k, n) => {
// 1. 记录结果集
const result = [];
// 2. 递归：index -> 索引，sum -> 当前和，path -> 路径
const recursion = (index, sum, path) => {
// 2.1 设置递归终止条件：如果它的路径长度等于 k
if (path.length === k) {
// 2.1.1 设置收割条件，当它的和为 n 的时候
if (sum === n) {
result.push(path.concat());
}
// 2.1.2 终止后续递归
return;
}
// 2.2 遍历 [index, 9]，从中挑选数字进入 path
for (let i = index; i <= 9; i++) {
// 2.2.1 如果 sum + i > n，表明和超标了，没必要下一轮递归
if (sum + i > n) {
break;
}
// 2.2.2 回溯常用，进进出出的套路
path.push(i);
recursion(i + 1, sum + i, path);
path.pop();
}
};
recursion(1, 0, []);
// 3. 返回结果
return result;
};
console.log(combinationSum3(3, 7)); // [ [ 1, 2, 4 ] ]
console.log(combinationSum3(3, 9)); // [ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]
