40. 组合总和 II（JS实现）

1 题目
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

2 思路
这道题思路还是利用回溯+剪枝的过程构造一棵树，不过由于不允许有重复，我们需要增加添加剪枝的条件，例如同一层级不允许出现相同的数

3代码
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
var arr = candidates.filter(function(i) { //剔除大于target的数
return i <= target;
})
arr.sort(function(a, b){
return a-b;
});
if (arr.length === 0) return []; //剔除后数组为空
if (arr[0] === target) return [[target]]; //*小的数等于target

var map = {};
var ans = [];
for (var i=0; i<arr.length; i++){
if (i > 0 && arr[i – 1] == arr[i]) continue; //同一层级不允许出现相同的数
getSum(arr[i], ” + arr[i], i+1); //从下一个数作为begin
}

function getSum(num, str, begin) {
if (num > target) return;

if (num === target) {
ans.push(str.split(‘-‘));
return;
}

for (var i=begin; i<arr.length; i++){
if (i > begin && arr[i – 1] == arr[i]) continue; //同一层级不允许出现相同的数
getSum(num+arr[i], str + ‘-‘ + arr[i], i+1);
}
}

return ans

};