给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
示例1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
};
个人解法
大佬思路:回溯算法 + 剪枝(Python 代码、Java 代码)
var combinationSum = function(candidates, target) {
var result = [];
function digui(target , arr){
for(var i = 0; i < candidates.length; i++){
if(target >= candidates[i]){
var arr2 = [...arr];
arr2.push(candidates[i]);
digui(target - candidates[i] , arr2);
}
}
if(target === 0){
result.push([...arr]);
}
return ;
}
digui(target , []);
//result有重复的的组合,进行去重
for(var i = 0; i < result.lengtg; i++){
result[i].sort((a,b) => a - b);
result[i] = result[i].join("-");
}
result = [...new Set(result)];
for(var i = 0; i < result.lengtg; i++){
result[i] = result[i].split("-");
}
return result;
};