39. Combination Sum
Tags
- Array
- Backtracking
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set
[2, 3, 6, 7]and target7, A solution set is:
[
[7],
[2, 2, 3]
]
1
2
3
4
2
3
4
题意：
给定一组候选数（C）和目标数（T），查找在C中的所有数的组合相加等于T。 相同的重复数可以从C无限次数选择。
分析：
本题跟题目1. Two Sum很相似，都是求出可以相加等于目标数，差异在于前者求位置坐标值，本题返回能组合的数字数组。所以，这个题目我们可以参考题目1. Two Sum的方式，通过目标值减去数组中小于它的值，直到可以刚好减完为止，然后，将期间的每个数值存储到数组中即可，区别在于本题需使用递归调用
思路：
根据上面的分析，基本有了一个大概的思路，具体到每一步，就是：
- 将数组升序排序
- 创建递归函数，目标值减去数组中的值，如果目标值还大于数组中的值，递归调用继续，如果等于就将这几个数字存入结果数组中
- 直到满足条件的数字循环完毕，返回结果数组
Js实现：
复杂度
时间复杂度O(n2)
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
let combinationSum = function(candidates, target) {
if(candidates ===null || candidates.length ===0){
return;
}
let result = [];
let ans = new Array(target);
candidates.sort(function(a,b){
return a - b;
});
//console.log(candidates);
fnResult(candidates,target,0,result,ans, 0);
return result;
};
function fnResult(cans,target,pos,result,ans,num) {
for( let i = pos;i <cans.length; i++){
if( target === cans[i]){
let aa = [];
for( let ii = 0; ii<num; ii++) {
aa.push(ans[ii]);
}
aa.push(cans[i]);
result.push(aa);
return;
}
else if(target > cans[i]){
ans[num] = cans[i];
fnResult(cans,target-cans[i],i,result,ans,num+1);
// console.log(ans);
}else
return ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39