40. 组合总和 II

[Geekhyt]

原题链接

回溯

本题在 39.组合总和 题的基础上加了1个限制条件：元素不可以重复使用了。

解题思路还是和 39 题一样，只需要在代码中改动如下几点即可：

1. 题目要求元素不能重复，需要去重，去重就要排序，因为排序后去重更方便。
2. 在枚举过程中，遇到重复项直接跳过。
3. 递归时改成 i + 1，避免与当前 i 重复。

const combinationSum2 = (candidates, target) => {
    candidates.sort((a, b) => a - b)
    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++) {
            if (i - 1 >= start && candidates[i - 1] === candidates[i]) continue
            arr.push(candidates[i])
            dfs(i + 1, arr, cur + candidates[i])
            arr.pop()
        }
    }
    dfs(0, [], 0)
    return res
}