回溯法的关键步骤：

1. 做出选择
2. 递归
3. 撤销选择

组合总和

题目

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

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

思路

1. 回溯法
2. 使用深度优先搜索（DFS）来遍历所有可能的组合
3. 使用回溯法来避免重复计算
4. 使用剪枝来优化算法

已 [2, 3, 6, 7] 和 target = 7 为例，画出回溯树：

          []
         /  \
       [2]   [3]
      /        \
   [2,2]      [3,3]
   /             \
[2,2,2]         [3,3,3]
   |
[2,2,3]  ✅ (sum = 7)

代码

const combinationSum = function (candidates, target) {
  const result = [];

  // 回溯函数
  const backtrack = (path, sum, start) => {
    // 剪枝：如果当前的和已经大于目标值，则直接返回
    if (sum > target) {
      return; // 剪枝
    }

    // 满足条件，找到一组解，加入结果集
    if (sum === target) {
      result.push([...path]);
      return;
    }

    /**
     * 遍历 candidates 数组，从 start 开始，允许重复使用 i
     * 我们使用 startIndex 来控制 不能选前面已经用过的数字，但可以重复使用当前数字
     */
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);                 // 做选择
      backtrack(path, sum + candidates[i], i);  // 递归尝试（可以重复选当前元素）
      path.pop();                               // 撤销选择（回溯的本质就是递归的逆过程，把最后一步“撤销”掉，试别的分支）
    }
  };

  backtrack([], 0, 0);

  return result;
};