给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。 解集不能包含重复的组合。
js
示例 1: 输入:candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]
示例 2: 输入:candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
js
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let result = [];
function backtrack(track, idx, sum) {
if (sum === target) return result.push([...track]);
if (sum > target) return;
for (let i = idx; i < candidates.length; i++) {
if (candidates[i] > target - sum) continue;
track.push(candidates[i]);
sum += candidates[i];
backtrack(track, i, sum);
sum -= candidates[i];
track.pop();
}
}
backtrack([], 0, 0);
return result;
};