CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解法
这题貌似见过很多次了，我一直使用之前的思路，是采用递归思路来写，到今天才发现之前的思路不对啊……害，还是老老实实使用回溯法来做，代码如下：(吐槽一个 C++ 的字符串处理)
class Solution {
public:
void dfs(vector<string>& ans, int n, string cur){
if(cur.length() == 2*n){
ans.push_back(cur);
return;
}
string temp = cur;
temp.push_back('(');
int sum = 0;
for(int i=0;i<temp.length();++i){
if(temp[i] == '(') sum++;
}
if(sum <= n) dfs(ans,n,temp);
temp[temp.length()-1] = ')';
sum = 0;
for(int i=0;i<temp.length();++i){
if(temp[i] == '(') sum++;
else sum--;
}
if(sum >= 0) dfs(ans,n,temp);
}
vector<string> generateParenthesis(int n) {
vector<string> ans;
string t;
dfs(ans,n,t);
return ans;
}
};