兰州网站建设专家,网站备案归哪里管,网站建设免费免代码,装饰工程网站模板下载文章目录 77. 组合题目描述回溯算法组合问题的剪枝操作 77. 组合
题目描述
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1#xff1a; 输入#xff1a;n 4, k 2 输出#xff1a; [ [2,4], [3,4],… 文章目录 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 201 k n
回溯算法 对回溯算法不太了解的同学可以看这篇文章回溯算法理论基础 该题目的详细解析可以看这篇文章第77题. 组合
看完这两篇文章后可能有同学看懂了[12][13][14]组合中234是如何删除回溯但没看懂1是如何删除回溯的可以看下图 代码如下
// 定义解决方案类
class Solution {
public:// 组合的主要公共接口返回所有可能的k个数的组合vectorvectorint combine(int n, int k) {// 从数字1开始进行回溯搜索backtracking(n, k, 1);// 返回搜索结果return result;}private:// 用来存放最终的组合结果vectorvectorint result;// 用于在递归过程中存放当前的组合路径vectorint 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注意下一次递归开始的索引是i1这样就不会有重复的组合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函数用于获取所有可能的组合vectorvectorint combine(int n, int k) {// 从数字1开始递归回溯搜索backtracking(n, k, 1);// 返回最终的结果列表return result;}private:// result用于存储所有的组合vectorvectorint result;// path用于在递归中构建每个组合vectorint 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进行下一层搜索下一次搜索从i1开始backtracking(n, k, i 1);// 回溯移除当前路径中的最后一个数字回到上一步尝试其它可能的数字path.pop_back();}// 当循环结束返回上一层递归return;}
};
在这段代码中
backtracking是一个递归函数用于深入每一层搜索可能的组合。path是一个临时向量用于存储当前递归路径上的组合。result是一个二维向量用于存储所有有效的k个数的组合。backtracking函数中的if语句是递归的终止条件即当path的大小等于k时将当前组合添加到结果中。循环中的i n - (k - path.size()) 1是一个关键的优化它保证了仅当还有足够的元素可供选择以填满剩余的位置时循环才会继续。这样可以减少不必要的递归调用提高算法的效率。
例如如果n4, k2并且目前path已经包含了一个元素假设是1则只需要在剩下的3个元素中选择一个2, 3, 或4而不需要再考虑选择1。如果当前path已经有两个元素则循环不再进行因为不需要更多元素。
