跳至主要內容

77. 组合


77. 组合open in new window

🟠   🔖  回溯  🔗 力扣open in new window LeetCodeopen in new window

题目

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 <= 20
  • 1 <= k <= n

题目大意

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

解题思路

可以使用回溯算法,通过递归的方式生成组合:

  1. 定义一个结果数组 res 和一个路径数组 track
  2. 使用回溯算法,通过递归函数 backtrack 遍历组合的所有可能性。
  3. backtrack 函数中,当路径数组的长度达到 k 时,将当前路径数组的副本加入结果数组。其中参数 start 控制遍历树枝的起始位置,避免产生重复的子集。
  4. 在每一层递归中,从 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;
};

相关题目

题号标题题解标签难度
39组合总和open in new window[✓]数组 回溯
46全排列open in new window[✓]数组 回溯