39. 组合总和

[Geekhyt]

原题链接

回溯

先明确，元素可以重复使用，但是组合不能重复。

1. 使用回溯法，不符合条件的情况进行剪枝。
2. 当 cur === target 时，拷贝 arr 推进结果集。
3. 从 start 开始遍历可选数组，选择当前数字后递归时注意要基于当前状态 i 继续选择，因为元素是可以重复进入集合的。
4. 撤销选择，恢复状态。

const combinationSum = (candidates, target) => {
    const res = []
    // start: 起点索引 arr: 当前集合 cur: 当前所求之和
    const dfs = (start, arr, cur) => {
        if (cur > target) return
        if (cur === target) {
            res.push(arr.slice())
            return
        }
        for (let i = start; i < candidates.length; i++) {
            arr.push(candidates[i])
            dfs(i, arr, cur + candidates[i])
            arr.pop()
        }
    }
    dfs(0, [], 0)
    return res
}