今日算法（回溯算法）

题目描述给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。组合从n个元素中选k个不考虑顺序即[1,2]和[2,1]视为同一个组合只保留一个可以按任何顺序返回答案核心思路回溯法DFS组合问题的本质是从有序序列中按顺序选元素避免重复用回溯法可以暴力且高效地枚举所有可能。核心逻辑路径保存用一个临时列表path保存当前正在构建的组合递归终止条件当path.size() k时说明找到了一个有效组合将其加入结果集选择与回溯从start位置开始选择元素避免选到前面的元素导致重复选择当前元素加入path递归进入下一层从i1位置继续选择回溯将当前元素从path中移除尝试下一个元素完整代码实现Ccppclass Solution { public: vectorvectorint combine(int n, int k) { vectorvectorint res; // 存储所有结果 vectorint path; // 存储当前正在构建的组合 backtrack(n, k, 1, path, res); return res; } private: // start: 本轮可以选择的起始位置避免重复 void backtrack(int n, int k, int start, vectorint path, vectorvectorint res) { // 1. 递归终止条件路径长度等于k找到一个有效组合 if (path.size() k) { res.push_back(path); return; } // 2. 剪枝优化剩余元素不足时无需继续遍历 // 还需要选 (k - path.size()) 个元素因此 i 最大只能到 n - (k - path.size()) 1 for (int i start; i n - (k - path.size()) 1; i) { // 3. 选择当前元素 path.push_back(i); // 4. 递归下一轮从 i1 开始选择避免重复 backtrack(n, k, i 1, path, res); // 5. 回溯撤销选择尝试下一个元素 path.pop_back(); } } };详细执行流程解析以示例n4, k2为例模拟回溯过程初始状态res []path []start 1递归过程第一层递归start1path[]循环i从1到3剪枝后4 - 2 1 3i1path [1]进入第二层递归start2第二层循环i从2到4i2path[1,2]长度为 2加入res回溯后path[1]i3path[1,3]加入res回溯后path[1]i4path[1,4]加入res回溯后path[1]回溯path[]i2path[2]进入第二层递归start3第二层循环i从3到4i3path[2,3]加入res回溯后path[2]i4path[2,4]加入res回溯后path[2]回溯path[]i3path[3]进入第二层递归start4第二层循环i4path[3,4]加入res回溯后path[3]回溯path[]最终结果res中包含所有C(4,2)6个组合[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]与示例输出一致。关键细节与易错点start参数的作用每次递归从start位置开始选择保证组合中的元素是递增的避免出现[2,1]这种重复组合。剪枝优化循环条件i n - (k - path.size()) 1是关键优化还需要选need k - path.size()个元素剩余可选元素从i到n共n - i 1个当n - i 1 need时无法凑齐k个元素无需继续遍历例如n4, k2当path.size()1时need1i最大为4当path.size()0时need2i最大为34-213避免了无效的i4循环。回溯操作的顺序必须先path.push_back(i)再递归最后path.pop_back()否则会导致path状态混乱。组合与排列的区别排列问题不需要start参数每次都从1开始选会出现重复顺序组合问题必须用start保证递增避免重复。复杂度分析时间复杂度\(O(C(n, k) \times k)\)组合数 \(C(n, k)\) 是所有有效组合的数量每个组合需要复制一次到结果集时间复杂度为 \(O(k)\)空间复杂度\(O(k)\)递归调用栈的深度等于k临时路径path的最大长度也为k不包含结果集的额外空间。拓展迭代法实现可选也可以用迭代法实现组合生成核心思想是不断扩展已有的组合cppclass Solution { public: vectorvectorint combine(int n, int k) { vectorvectorint res; // 初始化生成所有长度为1的组合 for (int i 1; i n; i) { res.push_back({i}); } // 扩展组合长度到k for (int len 2; len k; len) { vectorvectorint temp; for (auto comb : res) { int last comb.back(); // 从last1开始扩展保证递增 for (int i last 1; i n; i) { temp.push_back(comb); temp.back().push_back(i); } } res move(temp); } return res; } };总结组合问题的标准解法是带剪枝的回溯法核心是通过start参数保证组合的递增性避免重复同时通过剪枝优化减少无效的递归调用。这种方法是解决排列组合问题的通用模板后续的子集、全排列等问题都可以基于这个框架修改。