递归+回溯+leetcode原题讲解

116 阅读 0 评论 77 点赞

我是靠谱客的博主眼睛大百褶裙，这篇文章主要介绍递归+回溯+leetcode原题讲解，现在分享给大家，希望可以做个参考。

从大学就一直对递归很迷糊，想不清楚，最近刷leetcode这又是绕不过去的弯，索性这次认真研究一下并做个总结。

这里关于回溯讲解的比较容易懂。https://blog.csdn.net/versencoder/article/details/52071930

大概总结一下总有一个套路

定义一个全局结果用于保存最终的答案ans
定义一个辅助方法（函数）void backtrack(){},一般参数都有一个保存中间值的temp，其他参数根据实际题目定
接着分析递归出口，即什么时候将中间结果temp加入ans中

还有最重要的一点就是回溯，这个是为了还原现场，为了不影响下一次选择。这里讲的比较抽象，对于具体代码怎么体现我也迷糊了很久。下面就两道leetcode中具体的题目讲解一下。

题目一leetcode 39. combination Sum

这题在我添加的回溯法讲解中讲的很详细，属于典型的可以套用回溯的公式来。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> temp;
backtracking(candidates,0,target,temp);
return ans;
}
void backtracking(vector<int>& candidates,int start,int target, vector<int> &temp){
if(target < 0) return;//凑过头了Orz
if(target == 0){//刚好凑够^_^
ans.push_back(temp);//加到结果中
}
else{
for(int i = start; i < candidates.size(); i++){ //循环试探每个数0.0
temp.push_back(candidates[i]);//尝试加入=.=
backtracking(candidates,i,target-candidates[i],temp);//下一次凑的是target-candidates[i]啦～允许重复就还从i开始
temp.pop_back();//:
}
}
}
};

这么但看这一个程序没有问题，看不出来迷糊的地方，接着再看下一题。

leetcode 22. Generate Parentheses

这一题也是可以用回溯法，当然也可以用上面的套路实现。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<string>> ans;
vector<vector<string>> generateParenthesis(int n) {
vector<string> temp(n,"");
dfs(n,temp,0,0);
return ans;
}
void dfs(int n, vector<string> &temp,int left,int right){
if(temp.size()== 2*n){
ans.push_back(temp);
}
if(left < n) {
temp.push_back("(");
dfs(n,temp,left+1,right);//添加左括号的条件是左括号数量小于n
temp.pop_back();
}
if(right < left){
temp.push_back(")");
dfs(n,temp,left,right+1);//添加右括号的条件是右括号数小于左括号数
temp.pop_back();
}
}
};

这样写没问题，但是看了网上的答案，有一个看起来很简单的写法，但是不好理解，这也是我一开始迷糊的地方。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<string> ans;
vector<string> generateParenthesis(int n) {
string temp = "";
dfs(n,temp,0,0);
return ans;
}
void dfs(int n, string temp,int left,int right){
if(temp.length()== 2*n){
ans.push_back(temp);
}
if(left < n) dfs(n,temp+"(",left+1,right);//添加左括号的条件是左括号数量小于n
if(right < left) dfs(n,temp+")",left,right+1);//添加右括号的条件是右括号数小于左括号数
}
};

这里没有显示的体现回退的过程，一开始不理解，主要还是对变量作用域和函数参数传递这些基础知识不了解，在这里因为dfs里面传递的是temp+“（”,这样不会影响下一个分支的结果，对比上一个题的程序，之所以要回退就是因为有for循环，就相当于下一个分支，所以在下次选择之前要手动回退以保持之前的状态。而在这里在压栈的时候每一层已经保存了一个自己的temp，所以不需要手动回退，所以回溯的思想本身都是没有问题的，主要在于实现。