当前位置：首页 > news >正文

今日算法（回溯算法）

news 2026/5/24 0:37:11

题目描述

给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。

组合：从n个元素中选k个，不考虑顺序（即[1,2]和[2,1]视为同一个组合，只保留一个）
可以按任何顺序返回答案

核心思路：回溯法（DFS）

组合问题的本质是从有序序列中按顺序选元素，避免重复，用回溯法可以暴力且高效地枚举所有可能。

核心逻辑

路径保存：用一个临时列表path保存当前正在构建的组合
递归终止条件：当path.size() == k时，说明找到了一个有效组合，将其加入结果集
选择与回溯：
- 从start位置开始选择元素（避免选到前面的元素导致重复）
- 选择当前元素，加入path
- 递归进入下一层，从i+1位置继续选择
- 回溯：将当前元素从path中移除，尝试下一个元素

完整代码实现（C++）

cpp

class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; // 存储所有结果 vector<int> path; // 存储当前正在构建的组合 backtrack(n, k, 1, path, res); return res; } private: // start: 本轮可以选择的起始位置（避免重复） void backtrack(int n, int k, int start, vector<int>& path, vector<vector<int>>& 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. 递归：下一轮从 i+1 开始选择（避免重复） backtrack(n, k, i + 1, path, res); // 5. 回溯：撤销选择，尝试下一个元素 path.pop_back(); } } };

详细执行流程解析

以示例n=4, k=2为例，模拟回溯过程：

初始状态

res = []，path = []，start = 1

递归过程

第一层递归（start=1，path=[]）
- 循环i从1到3（剪枝后4 - 2 + 1 = 3）
- i=1：
  - path = [1]，进入第二层递归，start=2
  - 第二层循环i从2到4
    - i=2：path=[1,2]，长度为 2，加入res，回溯后path=[1]
    - i=3：path=[1,3]，加入res，回溯后path=[1]
    - i=4：path=[1,4]，加入res，回溯后path=[1]
  - 回溯，path=[]
- i=2：
  - path=[2]，进入第二层递归，start=3
  - 第二层循环i从3到4
    - i=3：path=[2,3]，加入res，回溯后path=[2]
    - i=4：path=[2,4]，加入res，回溯后path=[2]
  - 回溯，path=[]
- i=3：
  - path=[3]，进入第二层递归，start=4
  - 第二层循环i=4：path=[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个元素，无需继续遍历
- 例如n=4, k=2，当path.size()=1时，need=1，i最大为4；当path.size()=0时，need=2，i最大为3（4-2+1=3），避免了无效的i=4循环。
回溯操作的顺序必须先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，不包含结果集的额外空间。

拓展：迭代法实现（可选）

也可以用迭代法实现组合生成，核心思想是不断扩展已有的组合：

cpp

class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; // 初始化：生成所有长度为1的组合 for (int i = 1; i <= n; ++i) { res.push_back({i}); } // 扩展组合长度到k for (int len = 2; len <= k; ++len) { vector<vector<int>> temp; for (auto& comb : res) { int last = comb.back(); // 从last+1开始扩展，保证递增 for (int i = last + 1; i <= n; ++i) { temp.push_back(comb); temp.back().push_back(i); } } res = move(temp); } return res; } };