solution.md

# 括号生成

<p>数字 <code>n</code> 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 <strong>有效的 </strong>括号组合。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>n = 3<strong><br />输出：</strong>["((()))","(()())","(())()","()(())","()()()"]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>n = 1<strong><br />输出：</strong>["()"]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= n <= 8</code></li></ul>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    int n = 3;
    vector<string> res;
    res = sol.generateParenthesis(n);
    for (auto i : res)
        cout << i << endl;

    return 0;
}

```

## 答案

```cpp
class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {

        vector<string> 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<string> &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<string> &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<string> generateParenthesis(int n)
    {
        string s = "";
        vector<string> output;
        generateParenthesis(s, n, n, output);
        return output;
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<string> 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<string> generateParenthesis(int n)
    {
        if (n == 0)
            return vector<string>{""};
        string cur("(");
        backtrack(n, 1, cur);
        return res;
    }
};

```

### C

```cpp
class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> res;
        dfs("", 0, n, &res);
        return res;
    }

    void dfs(const string &path, int m, int n, vector<string> *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);
    }
};
```