- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
回溯
本题在39.组合总和 题的基础上加了1个限制条件：元素不可以重复使用了。
解题思路还是和 39 题一样，只需要在代码中改动如下几点即可：
- 题目要求元素不能重复，需要去重，去重就要排序，因为排序后去重更方便。
- 在枚举过程中，遇到重复项直接跳过。
- 递归时改成
i + 1，避免与当前 i 重复。
constcombinationSum2=(candidates,target)=>{candidates.sort((a,b)=>a-b)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++){if(i-1>=start&&candidates[i-1]===candidates[i])continuearr.push(candidates[i])dfs(i+1,arr,cur+candidates[i])arr.pop()}}dfs(0,[],0)returnres}