给定一个无重复元素的数组 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;
};