https://leetcode-cn.com/problems/generate-parentheses/
dfs回溯入门题。
忘了回溯是啥感觉了，赶紧找个入门题做一下体会体会。先贴一段话体会一下：
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
然后草稿纸上画一棵树，就能知道条件是啥了，开始写代码。
注意点：
- 满足退出条件 （✅），不满足退出的条件（忘写了，导致死循环）。
- vector<string> results在递归中是个全局的角色，所以要用引用，这样递归函数对它的修改才可以保存下来传递下去。不然就只是拷贝，没啥用。
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> results;
dfs(results, "", 0, 0, n);
return results;
}
void dfs(vector<string>& results, string str, int left, int right, int n) {
if (left == n && right == n) {
results.push_back(str);
return;
}
if (left > n || right > n) return; // 忘写了，导致死循环
if (left > right) {
dfs(results, str+'(', left+1, right, n);
dfs(results, str+')', left, right+1, n);
} else {
dfs(results, str+'(', left+1, right, n);
}
}
};
更简洁的写法参考一下，能写这么简洁，主要归功于条件想得十分清楚。
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
dfs(n, 1, 0, "(", res);
return res;
}
void dfs(int n, int left, int right, string str, vector<string>& res) {
if (left == n && right == n) {
res.push_back(str);
return;
}
if (left < right || left > n || right > n) return;
dfs(n, left + 1, right, str+'(', res);
dfs(n, left, right + 1, str+')', res);
}
};
