Skip to content
On this page

力扣题目链接

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

Released under the MIT License.