77\. Combinations
# 77. Combinations (opens new window)
# Description
Difficulty: Medium
Related Topics: Backtracking (opens new window)
Given two integers n
and k
, return all possible combinations of k
numbers out of the range [1, n]
.
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output:
[
[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
Example 2:
Input: n = 1, k = 1
Output: [[1]]
1
2
2
Constraints:
1 <= n <= 20
1 <= k <= n
# Solution
Language: JavaScript
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const ans = [];
const backtrack = (start = 1, path = []) => {
if (path.length === k) return ans.push([...path]);
for (let i = start; i <= n; i++) {
backtrack(i + 1, [...path, i]);
}
}
backtrack();
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20