# 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int n = 3;
vector res;
res = sol.generateParenthesis(n);
for (auto i : res)
cout << i << endl;
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
vector generateParenthesis(int n)
{
vector ans;
string s;
back(0, 2 * n, 0, 0, s, ans);
return ans;
}
void back(int left, int right, int l_n, int r_n, string &s, vector &ans)
{
if (r_n > l_n || l_n > right)
return;
if (left == right)
{
ans.push_back(s);
return;
}
s += '(';
l_n++;
left++;
back(left, right, l_n, r_n, s, ans);
s.erase(s.end() - 1);
l_n--;
s += ')';
r_n++;
back(left, right, l_n, r_n, s, ans);
s.erase(s.end() - 1);
r_n--;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
void generateParenthesis(string i, int left, int right, vector &output)
{
if (left == 0 && right == 0)
{
output.push_back(i);
return;
}
if (left > 0)
{
generateParenthesis(i + '(', left - 1, right, output);
}
if (left < right)
{
generateParenthesis(i + ')', left, right - 1, output);
}
}
vector generateParenthesis(int n)
{
string s = "";
vector output;
generateParenthesis(s, n, n, output);
return output;
}
};
```
### B
```cpp
class Solution
{
public:
vector res;
void backtrack(int n, int key, string cur)
{
if (key < 0 || key > n)
return;
if (cur.size() == 2 * n)
{
if (key == 0)
res.push_back(cur);
return;
}
backtrack(n, key - 1, cur + ')');
backtrack(n, key + 1, cur + '(');
}
vector generateParenthesis(int n)
{
if (n == 0)
return vector{""};
string cur("(");
backtrack(n, 1, cur);
return res;
}
};
```
### C
```cpp
class Solution
{
public:
vector generateParenthesis(int n)
{
vector res;
dfs("", 0, n, &res);
return res;
}
void dfs(const string &path, int m, int n, vector *res)
{
if (m == 0 && n == 0)
{
if (!path.empty())
res->push_back(path);
return;
}
if (n > 0)
dfs(path + '(', m + 1, n - 1, res);
if (m > 0)
dfs(path + ')', m - 1, n, res);
}
};
```