class Solution {
public:
    vector<string> ans;
    // 在任意前缀中左括号的数量大于等于右括号的数量
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return ans;
    }
    void dfs(int n, int lc, int rc, string seq)
    {
        if(lc==n&&rc==n)ans.push_back(seq);
        else{
            if(lc<n)dfs(n, lc+1, rc, seq+'(');
            if(rc<n&&lc>rc)dfs(n, lc, rc+1, seq+')');
        }
    }
};