组合总和 III(JS实现)

组合总和 III(JS实现)

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]]

链接:https://leetcode-cn.com/problems/combination-sum-iii

2 思路
这道题还是考察回溯+剪枝,整体的思路就是构造一棵树,*后能到达叶子节点的路径就是有效的结果

3代码
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
const res = [];
if (n < 1 || k < 1 || k > 9) return res;
let nums = [1,2,3,4,5,6,7,8,9];

function d(arr, index, num, begin) {
for (let i=begin; i<9; i++) {
let temp = num – nums[i];
if (temp < 0) break;

if (temp > 0 && index > 1) {
let tempArr = arr.slice();
tempArr.push(nums[i]);
d(tempArr, index-1, temp, i+1);
} else if (temp === 0 && index === 1) {
let tempArr = arr.slice();
tempArr.push(nums[i]);
res.push(tempArr);
}
}
}

d([], k, n, 0);

return res;
};