回溯题目的套路总结

媒介    

昨天写完了LeeCode的7，8道回溯算法的题目，写一下总结，这类题目的共同特点就是暴力搜索题目，分列组合或者递归，罗列出所有大概的答案，思绪很简单，实现起来的套路也很通用，一回溯题目为例，常用的是构建一颗搜索树，bfs，dfs
模板
函数名（递归参数）
if（这里是终止条件）
{
一般达到终止条件就需要把答案放入
}
for（）
{
push，压入元素，
函数名（递归参数）//这里是往下一层举行递归
pop递归失败，弹出压入的元素
}
这里是写了一个大致的模板，实际的题目还要对照画出一颗树形图更合适，并且方便明确
例题

这里参考力扣的括号生成，画出搜索树

这道题的思绪就是暴力搜索，我们遍历所有大概的括号搜索情况，题目的关键就是构建回溯函数
回溯函数构建的正确，才能得到正确的分支

例题1的参考代码

1. class Solution {
2. public:
3.     vector<string>res;
4.     vector<string> generateParenthesis(int n) {
5.         string s;
6.         dfs(n, 0, 0, s);
7.         return res;
8.     }
9.     void dfs(int n, int l, int r, string s)
10.     {
11.         if (l == n && r == n)res.push_back(s);
12.         else {
13.             if (l < n)dfs(n, l + 1, r, s + "(");
14.             if (r<n && l>r)dfs(n, l, r + 1, s + ")");
15.         }
16.     }
17. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。