dfs搜索

括号序列定理1：任意前缀中(数量 >= )数量
括号序列定理2：左右括号数量相等

搜索顺序是枚举每一位填什么，最终答案一定是有n个左括号和n个右括号组成。

1.填左括号: ( 的数量 < n ，则表示可以填左括号
2.填右括号:) 的数量 < n，并且已经填的(的数量>)的数量，则可以填右括号

$ 时间复杂度是卡特兰数 $

参考文献

lc究极班

AC代码

class Solution {
public:
    vector<string> res;

    void dfs(int n, string path, int l, int r){
        if (path.size() == n * 2){
            res.push_back(path);
            return ;
        }
        //判断是否填左括号
        if (l < n) dfs(n, path + "(", l + 1 , r);
        //判断是否填右括号
        if (r < n && l > r) dfs(n, path + ")", l, r + 1);
    }

    vector<string> generateParenthesis(int n) {
        dfs(n, "", 0, 0);
        return res;
    }
};