-
Notifications
You must be signed in to change notification settings - Fork 25
/
0077-combinations.js
56 lines (48 loc) · 1.07 KB
/
0077-combinations.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
52
53
54
55
56
// 77. Combinations
// Medium 40%
// Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
// For example,
// If n = 4 and k = 2, a solution is:
// [
// [2,4],
// [3,4],
// [2,3],
// [1,2],
// [1,3],
// [1,4],
// ]
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
const combine = function(n, k) {
const res = []
const iter = (comb, i) => {
if (comb.length === k) res.push([...comb])
else {
for (; i <= n; i++) {
comb.push(i)
iter(comb, i + 1)
comb.pop()
}
}
}
iter([], 1)
return res
}
;[
[2, 1],
[4, 2],
[5, 3],
].forEach(args => {
console.log(combine(...args))
})
// Solution:
// 求组合数,即求出从数字 1~n 中任取 k 个不同的数的全部组合。
// 使用 DFS 来解决。
// 每个组合中的数都按从小到大的顺序进行选择。
// 每个位置上的数字不断按从小到大的顺序进行更换。
// 这样可以防止出现重复的组合。
// DFS 确保遍历到每一个组合。
// Submission Result: Accepted