39. 组合总和（JS实现）

1 题目
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

2 思路
这道题思路是主要还是利用回溯+剪枝的过程构造一棵树，其中叶子节点就是*终的结果，我们可以先将数组排序并筛选剔除，减少迭代的次数

3代码
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = 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++){
getSum(arr[i], ” + arr[i]);
}

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

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

for (var i=0; i<arr.length; i++){
getSum(num+arr[i], str + ‘-‘ + arr[i]);
}
}

return ans.filter(function(i) {
i.sort(function(a, b){
return a-b;
});
var key = i.join(”);
if (map[key]) return false;
map[key] = true;
return true;
});
};