40. Combination Sum II
Given a collection of candidate numbers (candidates
) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sums to target
.
Each number in candidates
may only be used once in the combination.
Note:
- All numbers (including
target
) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates =[10,1,2,7,6,1,5]
, target =8
, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]
题意:获取所有的排列组合,使得所有项加起来等于target,可选项不能重复,结果不能重复
代码如下:
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum2 = function(candidates, target) { var res={}; var curr=[]; candidates.sort((a,b)=>a-b); backTrack(res,curr,candidates,target,0); return Object.values(res); }; function backTrack(res,curr,candidates,target,start){ if(target>0){ for(var i=start;i<candidates.length && target>=candidates[i];i++){ curr.push(candidates[i]); backTrack(res,curr,candidates,target-candidates[i],i+1); curr.pop(); } }else if(target==0){ let str=curr.join('') res[str]=[...curr]; } }