39.Combination Sum

/**
 * @param {number[]} candidates - 无重复元素的正整数数组
 * @param {number} target - 目标和
 * @return {number[][]} - 所有和为目标值的组合列表
 */
var combinationSum = function (candidates, target) {
  // 对应原Python的ans，存储最终结果
  let ans = []
  // 对应原Python的path，存储当前回溯路径
  let path = []

  /**
   * 深度优先搜索函数（对应原Python的dfs）
   * @param {number} i - 当前遍历到的候选数组下标（原Python的i）
   * @param {number} left - 距离目标值剩余的数值（原Python的left）
   */
  const dfs = (i, left) => {
    // 递归终止条件1：剩余值为0，找到合法组合
    if (left === 0) {
      // 拷贝当前路径加入结果（避免后续修改path影响结果）
      ans.push([...path])
      return
    }

    // 递归终止条件2：遍历完所有候选数 或 剩余值小于0（路径和超目标值）
    if (i === candidates.length || left < 0) {
      return
    }

    // 分支1：不选当前下标i的数，递归下一个下标
    dfs(i + 1, left)

    // 分支2：选择当前下标i的数
    // 将当前数加入路径
    path.push(candidates[i])
    // 递归（下标不变，可重复选当前数；剩余值减去当前数）
    dfs(i, left - candidates[i])
    // 回溯：恢复path状态，移除最后加入的数
    path.pop()
  }

  // 初始调用：从下标0、剩余值为target开始
  dfs(0, target)

  return ans
}