0039. 组合总和.md

39. 组合总和

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/combination-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

回溯 深度优先 dfs

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  const result = []
  const dfs = (tar, comb, ind) => {
    if (ind === candidates.length) {
      return
    }

    // 可以选择跳过当前的数，用下一个数（这里相当于是回溯了）
    dfs(tar, comb, ind + 1)

    // 也可以选择用当前的数
    // 当前的数可以被用的条件是：tar - candidates[ind] >= 0
    const current = candidates[ind]
    const diff = tar - current
    if (diff > 0) {
      dfs(diff, [...comb, current], ind)
    } else if (diff === 0) {
      result.push([...comb, current])
    }
  }

  dfs(target, [], 0)

  return result
};