class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s;
        solve(s, 0, 0, n);
        return ans;
    }

    void solve(string &s, int lCnt, int rCnt, const int &n) {  // lCnt: 左括号的数目, rCnt: 有括号的数目
        if(lCnt == n && rCnt == n) {
            ans.emplace_back(s);
            return ;
        }
        if(lCnt == rCnt) {      // 左右括号数目一样, 只能放左括号
            s.push_back(‘(‘);
            solve(s, lCnt + 1, rCnt, n);
            s.pop_back();
        } else if(lCnt == n) {  // 左括号满了, 只能放右括号
            s.push_back(‘)‘);
            solve(s, lCnt, rCnt + 1, n);
            s.pop_back();
        } else {    // 都可以放
            s.push_back(‘(‘);
            solve(s, lCnt + 1, rCnt, n);
            s.pop_back();
            s.push_back(‘)‘);
            solve(s, lCnt, rCnt + 1, n);
            s.pop_back();
        }
    }

    vector<string> ans;
};