Repository navigation
40. 组合总和 II #31
Description
回溯
本题在 39.组合总和 题的基础上加了1个限制条件：元素不可以重复使用了。
解题思路还是和 39 题一样，只需要在代码中改动如下几点即可：
- 题目要求元素不能重复，需要去重，去重就要排序，因为排序后去重更方便。
- 在枚举过程中，遇到重复项直接跳过。
- 递归时改成
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
}
Activity