77. Combinations
77. Combinations
题目
Given two integers n and k, return all possible combinations of knumbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= n
题目大意
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
解题思路
可以使用回溯算法，通过递归的方式生成组合：
- 定义一个结果数组
res和一个路径数组track。 - 使用回溯算法，通过递归函数
backtrack遍历组合的所有可能性。 - 在
backtrack函数中，当路径数组的长度达到k时，将当前路径数组的副本加入结果数组。其中参数start控制遍历树枝的起始位置，避免产生重复的子集。 - 在每一层递归中，从
start开始遍历数字，将当前数字加入路径数组，然后递归调用下一层，最后弹出当前数字，回溯到上一层。
- 时间复杂度：
O(n! / (k!(n-k)!))，因为这个问题的解的数量是从n个不同元素中选择k个元素的方式数。 - 空间复杂度：
O(k * n! / (k!(n-k)!)) + O(k)=O(k * n! / (k!(n-k)!))，其中n! / (k!(n-k)!)表示从n个元素中选择k个的组合数。由于n! / (k!(n-k)!) < n! / ((n / 2)!)^2，因此整体空间复杂度可以简化为O(k * n! / ((n / 2)!)^2)。
代码
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
let res = [];
let track = [];
const backtrack = (start) => {
if (track.length == k) {
res.push([...track]);
return;
}
for (let i = start; i <= n; i++) {
track.push(i);
backtrack(i + 1);
track.pop();
}
};
backtrack(1);
return res;
};