39.组合总和

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字之和为目标数 target 的所有 不同组合，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

示例 2：

输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入：candidates = [2], target = 1
输出：[]

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

解析

回溯法，每次可以选择当前数字（可重复选）或跳到下一个数字。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  const result = [];
  candidates.sort((a, b) => a - b);

  function backtrack(start, path, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break; // 剪枝
      path.push(candidates[i]);
      backtrack(i, path, remaining - candidates[i]); // i 不加 1，允许重复选
      path.pop();
    }
  }

  backtrack(0, [], target);
  return result;
};

先排序再回溯，利用剪枝优化性能。注意递归时传入 i 而非 i+1，因为允许重复选取同一数字。