回溯题目的套路总结
前言
昨天写完了LeeCode的7，8道回溯算法的题目，写一下总结，这类题目的共同特点就是暴力搜索问题，排列组合或者递归，枚举出所有可能的答案，思路很简单，实现起来的套路也很通用，一回溯问题为例，常用的是构建一颗搜索树，bfs，dfs
模板
函数名（递归参数）
if（这里是终止条件）
{
一般达到终止条件就需要把答案放入
}
for（）
{
push，压入元素，
函数名（递归参数）//这里是往下一层进行递归
pop递归失败，弹出压入的元素
}
这里是写了一个大致的模板，实际的题目还要对照画出一颗树形图更合适，并且方便理解
例题
这里参考力扣的括号生成，画出搜索树
这道题的思路就是暴力搜索，我们遍历所有可能的括号搜索情况，问题的关键就是构建回溯函数
回溯函数构建的正确，才能得到正确的分支
例题1的参考代码
class Solution {
public:
vector<string>res;
vector<string> generateParenthesis(int n) {
string s;
dfs(n, 0, 0, s);
return res;
}
void dfs(int n, int l, int r, string s)
{
if (l == n && r == n)res.push_back(s);
else {
if (l < n)dfs(n, l + 1, r, s + "(");
if (r<n && l>r)dfs(n, l, r + 1, s + ")");
}
}
};原文地址：https://blog.csdn.net/qq_51286996/article/details/140602625
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！