39. 组合总和 #30
Description
回溯
先明确，元素可以重复使用，但是组合不能重复。
- 使用回溯法，不符合条件的情况进行剪枝。
- 当
cur === target时，拷贝 arr 推进结果集。 - 从 start 开始遍历可选数组，选择当前数字后递归时注意要基于当前状态 i 继续选择，因为元素是可以重复进入集合的。
- 撤销选择，恢复状态。
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
}