- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
回溯
先明确，元素可以重复使用，但是组合不能重复。
- 使用回溯法，不符合条件的情况进行剪枝。
- 当
cur === target时，拷贝 arr 推进结果集。 - 从 start 开始遍历可选数组，选择当前数字后递归时注意要基于当前状态 i 继续选择，因为元素是可以重复进入集合的。
- 撤销选择，恢复状态。
constcombinationSum=(candidates,target)=>{constres=[]// start: 起点索引 arr: 当前集合 cur: 当前所求之和constdfs=(start,arr,cur)=>{if(cur>target)returnif(cur===target){res.push(arr.slice())return}for(leti=start;i<candidates.length;i++){arr.push(candidates[i])dfs(i,arr,cur+candidates[i])arr.pop()}}dfs(0,[],0)returnres}