77. 组合
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
示例 2：
提示：
- 1 <= n <= 20
- 1 <= k <= n
回溯算法
看完这两篇文章后，可能有同学看懂了[12]，[13]，[14]组合中2，3，4是如何删除（回溯），但没看懂1是如何删除（回溯）的可以看下图：
代码如下：
// 定义解决方案类
class Solution {
public:
// 组合的主要公共接口，返回所有可能的k个数的组合
vector<vector<int>> combine(int n, int k) {
// 从数字1开始进行回溯搜索
backtracking(n, k, 1);
// 返回搜索结果
return result;
}
private:
// 用来存放最终的组合结果
vector<vector<int>> result;
// 用于在递归过程中存放当前的组合路径
vector<int> path;
// 回溯函数，递归生成所有可能的组合
void backtracking(int n, int k, int startindex) {
// 如果当前路径的长度等于k，说明找到了一个长度为k的组合
if (path.size() == k) {
// 将当前路径加入到结果集中
result.push_back(path);
// 返回上一层递归
return;
}
// 从startindex开始，尝试所有可能的下一个元素
for (int i = startindex; i <= n; i++) {
// 将当前元素加入到当前路径
path.push_back(i);
// 递归调用backtracking，注意下一次递归开始的索引是i+1，这样就不会有重复的组合
backtracking(n, k, i + 1);
// 将当前元素从路径中移除，也称为回溯
path.pop_back();
}
// 如果循环结束，返回上一层递归
return;
}
};
在这个代码中：
- 类Solution包含一个公共成员函数combine，它初始化回溯过程并返回结果。
- backtracking是一个递归函数，用于执行回溯搜索。它接受当前数字的范围n，组合的长度k，以及当前搜索的起始索引startindex。
- 私有成员result用于存储最终的组合结果；path用于在递归过程中跟踪当前的组合路径。
- 在backtracking函数中，通过循环遍历startindex到n的所有数字，并将每个数字添加到当前路径path中。每添加一个数字，就递归调用backtracking，直到达到组合的长度k。到达长度k时，将当前路径path添加到结果列表result中。
- 在每次递归调用之后，path需要回溯，即移除最后一个元素，以便下一次递归调用可以尝试新的数字组合。
组合问题的剪枝操作
详细解析可以看这篇文章：77.组合优化
代码如下：
// 定义Solution类，这是一个解决方案类
class Solution {
public:
// combine函数用于获取所有可能的组合
vector<vector<int>> combine(int n, int k) {
// 从数字1开始递归回溯搜索
backtracking(n, k, 1);
// 返回最终的结果列表
return result;
}
private:
// result用于存储所有的组合
vector<vector<int>> result;
// path用于在递归中构建每个组合
vector<int> path;
// backtracking是核心的递归回溯函数
void backtracking(int n, int k, int startindex) {
// 如果当前路径中的数字数量已经达到k个，则将当前路径保存到结果列表中
if (path.size() == k) {
result.push_back(path);
return;
}
// 进行循环，尝试所有可能的数
// 注意：这里使用了优化，减少了搜索的范围，避免了不必要的递归
// n - (k - path.size()) + 1是剪枝后的上界
for (int i = startindex; i <= n - (k - path.size()) + 1; i++) {
// 将当前数字i加入到当前组合路径中
path.push_back(i);
// 递归调用backtracking，进行下一层搜索，下一次搜索从i+1开始
backtracking(n, k, i + 1);
// 回溯，移除当前路径中的最后一个数字，回到上一步，尝试其它可能的数字
path.pop_back();
}
// 当循环结束，返回上一层递归
return;
}
};
在这段代码中：
- backtracking是一个递归函数，用于深入每一层搜索可能的组合。
- path是一个临时向量，用于存储当前递归路径上的组合。
- result是一个二维向量，用于存储所有有效的k个数的组合。
- backtracking函数中的if语句是递归的终止条件，即当path的大小等于k时，将当前组合添加到结果中。
例如，如果n=4, k=2，并且目前path已经包含了一个元素（假设是1），则只需要在剩下的3个元素中选择一个（2, 3, 或4），而不需要再考虑选择1。如果当前path已经有两个元素，则循环不再进行，因为不需要更多元素。