0077.组合
难度：🟡 中等
标签：数组、回溯
链接：77. 组合
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
解题思路
核心思想
本题的目标是在 1 到 n 的范围内，找出所有包含 k 个数字的组合。与“排列”不同，组合是不关心元素顺序的（例如 [1,2] 和 [2,1] 是同一个组合）。解决这类问题的标准算法是 回溯法。
思路选择
回溯法（深度优先搜索 DFS） 是解决此问题的经典思路。我们把生成组合的过程看作是在一棵决策树上进行探索。为了避免产生重复的组合，我们需要确保在每一层选择的数字都比上一层选择的数字要大。
我们可以定义一个递归函数，它负责从一个给定的起始数字开始，继续向组合中添加新的数字。
通过传递一个起始索引
startIndex，我们保证了搜索是单向的，从而避免了重复。
关键步骤
定义回溯函数：创建一个递归函数，例如
backtrack(startIndex, path)。startIndex: 表示本轮选择应该从数字几开始（例如，如果上一轮选了 2，这一轮就从 3 开始选）。path: 一个数组，存储当前正在构建的组合。
设置终止条件 (Base Case)：当
path的长度等于k时，说明我们已经构建了一个完整的组合，将其副本加入结果集，并结束当前递归。循环与递归： a. 从
startIndex开始，循环到n。 b. 剪枝优化：我们可以进行一个重要的剪枝。如果剩余需要选择的数字数量(k - path.length)大于从当前数字到n的剩余可选数字数量(n - i + 1)，那么无论如何也凑不够k个数了，可以直接结束当前循环。 c. 做出选择：将当前数字i推入path。 d. 进入下一层决策：以i + 1作为新的起始数字，递归调用回溯函数。 e. 撤销选择：当深层递归返回后，将之前加入的数字从path中弹出 (path.pop())，以便回溯到上一状态。
代码实现
// 优化前的回溯辅助函数
var backTracking = function (choices, path, results, current, target) {
if (path.length === target) {
results.push([...path]);
return;
}
// 从当前位置开始，避免重复组合
for (let i = current; i < choices.length; i++) {
path.push(choices[i]);
backTracking(choices, path, results, i + 1, target);
path.pop();
}
}
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
// 预先生成一个从 1 到 n 的数组，这步可以省略
let choices = [];
for (let i = 1; i <= n; i++) {
choices.push(i);
}
let results = [];
backTracking(choices, [], results, 0, k);
return results;
};
复杂度分析
时间复杂度：O(C(n, k) × k) 其中 C(n, k) 是从 n 个元素中取 k 个的组合数。我们需要找到所有组合，对于每个组合，需要 O(k) 的时间来将其复制到结果数组中。
空间复杂度：O(k) 不考虑存储结果的数组，空间复杂度主要由递归调用栈的深度决定，最深为 k。
相关题目
总结
本题是回溯算法求解“组合”问题的标准模型。与“排列”问题的主要区别在于，组合问题需要通过传递起始索引来避免元素顺序不同但成员相同的重复解。理解和应用剪枝是优化此类回溯问题的关键技巧。