代码随想录 (programmercarl.com)
一、什么是回溯算法
回溯算法是一种通用的算法设计技巧,特别适用于解决组合、排列、子集等问题。它通过逐步构建解决方案,并在发现部分解决方案无效时撤销(回溯)部分计算,从而寻找所有可能的解决方案。
回溯算法的基本思想是通过深度优先搜索(DFS)遍历所有可能的解空间,当发现某条路径不符合条件时,返回到上一步,尝试其他路径。
二、回溯法解决的问题
回溯法,一般可以解决如下几种问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
三、如何理解回溯法
回溯法解决的问题都可以抽象为树形结构,因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度就构成了树的深度。
递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。
四、回溯三部曲
- 回溯函数模板返回值以及参数
void backtracking(参数)
- 回溯函数终止条件
if (终止条件) { 存放结果; return; }
- 回溯搜索的遍历过程
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 }
完整模板如下
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }
力扣题目
代码解决
class Solution {
public:
vector<vector<int>> result; // 存储所有组合结果
vector<int> path; // 存储当前组合路径
// 回溯函数
void backtracking(int n, int k, int index) {
// 如果当前路径长度等于k,则找到一个有效组合,将其加入结果集
if (path.size() == k) {
result.push_back(path);
return;
}
// 从当前索引开始遍历到n
for (int i = index; i <= n; i++) {
path.push_back(i); // 选择当前数加入组合路径
backtracking(n, k, i + 1); // 递归调用,继续选择下一个数
path.pop_back(); // 撤销选择,回溯到上一步
}
}
// 主函数,生成1到n中k个数的所有组合
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1); // 从1开始进行回溯
return result; // 返回所有组合结果
}
};
代码使用了回溯算法。主要思路是使用一个递归函数 backtracking
来生成所有可能的组合。在每次递归调用中,我们选择一个数并将其添加到当前组合中,然后递归地继续选择下一个数。如果当前组合的长度达到k,则将其添加到结果集中。在每次递归调用之前,我们通过将当前数从路径中移除来实现回溯。
这里简要解释一下代码的工作流程:
- 定义两个全局变量
result
和path
,分别用于存储所有组合结果和当前组合路径。 - 定义一个辅助函数
backtracking
,它接受三个参数:n(数列的上限)、k(组合中元素的数量)和当前选择的起始索引index
。 - 如果当前路径长度等于k,则找到了一个有效的组合,将其加入结果集
result
。 - 从当前索引
index
开始遍历到n,对于每个数,将其添加到路径path
中,然后递归调用backtracking
函数继续选择下一个数。 - 在每次递归调用之前,通过
path.pop_back()
撤销选择,实现回溯。 - 在
combine
函数中,调用backtracking
函数开始生成所有可能的组合,并返回结果集result
。
这个算法的时间复杂度是 O(n * k),因为需要生成所有可能的k个数的组合。空间复杂度也是 O(n * k),因为需要存储所有组合和递归调用的栈。
标签:组合,递归,路径,190,力扣,result,回溯,backtracking From: https://blog.csdn.net/weixin_63779802/article/details/139861583