# 39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
let result = []
const dfs = (index,sum,tmpArray) => { // index为当前起点的索引，sum和，tmpArray结果集合
if(sum === target) {
result.push(tmpArray.slice())
}
if(sum > target) {
return
}
for(let i=index;i<candidates.length;i++) { // 枚举当前可选的数，从index开始
tmpArray.push(candidates[i]) // 选这个数
dfs(i,sum+candidates[i],tmpArray) // 基于此，继续选择，传i，下一次就不会选到i左边的数
tmpArray.pop() // 撤销选择，回到选择candidates[i]之前的状态，继续尝试选同层右边的数
}
}
dfs(0,0,[])
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TIP
只要限制下一次选择的起点，是基于本次的选择，这样下一次就不会选到本次选择的同层左边的数。即通过控制 for 遍历的起点，去掉会产生重复组合的选项。
# 77.组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
let result = []
const dfs = (start,tmpArray) => {
if(tmpArray.length === k) {
result.push(tmpArray.slice())
return
}
for(let i=start;i<=n;i++) {
tmpArray.push(i)
dfs(i+1,tmpArray)
tmpArray.pop()
}
}
dfs(1,[])
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 216.组合总和III
找出所有相加之和为
n的k个数的组合。组合中只允许含有1 - 9的正整数，并且每种组合中不存在重复的数字。
输入: k = 3, n = 7
输出: [[1,2,4]]
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
1
2
3
4
5
2
3
4
5
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
let result = []
const dfs = (index,sum,tmpArray) => {
if(tmpArray.length === k) {
if(sum === n) {
result.push(tmpArray.slice())
}
return
}
for(let i=index;i<=9;i++) {
tmpArray.push(i)
dfs(i+1,sum+i,tmpArray)
tmpArray.pop()
}
}
dfs(1,0,[])
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 组合总和II
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
let result = []
candidates.sort((a,b) => a-b)
let dfs = (index,tmpArray,sum) => {
if(sum>=target) {
// 爆掉了就不用选了
if(sum === target) {
result.push(tmpArray.slice())
}
return //结束当前的递归
}
for(let i=index;i<candidates.length;i++) {
if(i-1>=index && candidates[i-1]===candidates[i]){
continue; // 当前选项和左选项一样就跳过，因为每个数字只使用一次
}
tmpArray.push(candidates[i])
dfs(i+1,tmpArray,sum+candidates[i])
tmpArray.pop()
}
}
dfs(0,[],0)
return result
};
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
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
和39题的区别：
