文章目录
- 77. 组合
- 题目描述
- 回溯算法
- 组合问题的剪枝操作
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 <= 20
- 1 <= k <= n
回溯算法
-
对回溯算法不太了解的同学可以看这篇文章:回溯算法理论基础
-
该题目的详细解析可以看这篇文章:第77题. 组合
看完这两篇文章后,可能有同学看懂了[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时,将当前组合添加到结果中。
- 循环中的i <= n - (k - path.size()) + 1是一个关键的优化,它保证了仅当还有足够的元素可供选择以填满剩余的位置时,循环才会继续。这样可以减少不必要的递归调用,提高算法的效率。
例如,如果n=4, k=2,并且目前path已经包含了一个元素(假设是1),则只需要在剩下的3个元素中选择一个(2, 3, 或4),而不需要再考虑选择1。如果当前path已经有两个元素,则循环不再进行,因为不需要更多元素。