2023年11月19日

[Leetcode] 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

**示例 1：****输入：**n = 3 输出：[”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

**示例 2：****输入：**n = 1 输出：[”()”]

提示：

1 <= n <= 8

class Solution {
private:
    // (
    // ((
    // ((()
    // ((())
    // ((())) ok
    // ((())
    // ((()
    // (((
    // (()
    // (()(
    // (()()
    // (()())
    //
    string cur_res;
    vector<string> res;
    void dfs(const int &n, int left, int right)
    {
        if (cur_res.size() == n * 2)
        {
            res.push_back(cur_res);
            return;
        }
        if (left < n)
        {
            cur_res.push_back('(');
            dfs(n, left + 1, right);
            cur_res.pop_back();
        }
        if (right < left)
        {
            cur_res.push_back(')');
            dfs(n, left, right + 1);
            cur_res.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        dfs(n,0,0);
        return res;
    }
};