-
Notifications
You must be signed in to change notification settings - Fork 43
/
39. 组合总和.js
51 lines (44 loc) · 1.24 KB
/
39. 组合总和.js
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
40
41
42
43
44
45
46
47
48
49
50
51
/*
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
*/
/**
*
* 回溯
* 为了不重复,现将待选择的candidates进行排序,下一次选择的开始都从当前的index开始
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let res = [];
candidates = candidates.sort((a, b) => {
return a - b;
});
dfs(candidates, target, 0, [], res);
return res;
};
function dfs(candidates, target, start, solution, res) {//start的目的是为了不再使用已选中的元素
if (target === 0) {
res.push(solution.slice());
return
} else if (target < 0) {
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > target) continue;
solution.push(candidates[i]);
dfs(candidates, target - candidates[i], i, solution, res);
solution.pop();
}
}