[39] 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

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

]

提示：

1 <= candidates.length <= 30

1 <= candidates[i] <= 200

candidate 中的每个元素都是独一无二的。

1 <= target <= 500

这也是一道经典的回溯题，想到了使用回溯这道题就没什么难点了，需要注意的是剪枝的方法。

当发现当前选择的元素和已经大于 target，则这一颗树已经不可能组合出 target 了，因此进行剪枝。

function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = [];
  let currSum: number = 0;
  backtrack([], 0);
  return res;

  function backtrack(path: number[], start: number) {
    // 满足要求，输出
    if (currSum === target) {
      res.push([...path]);
      return;
    }
    // 当前和已经大于 target，则直接剪枝
    if (currSum > target) {
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      // 做选择
      currSum += candidates[i];
      path.push(candidates[i]);
      // 回溯
      backtrack(path, i);
      // 撤销选择
      currSum -= candidates[i];
      path.pop();
    }
  }
}