class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        // 1、记录左右括号的数目
        int left = n;
        int right = n;
        string curStr = "";
        helper(left, right, curStr, res);
        return res;
    }
    void helper(int left, int right, string& curStr, vector<string>& res) {
        if (left == 0 && right == 0) {
            res.emplace_back(curStr);
            return;
        }
        if (left > 0) {
            string temp = curStr;
            // 2、先塞一个左括号进去
            curStr += '(';
            left --; // 数量变更
            // 3、此时塞右括号
            // 右括号的数目比左括号少，那么肯定存在不合法的匹配，因为先塞左括号
            if (left < right) {
                helper(left, right, curStr, res);
                // 4、状态还原
                left ++;
                curStr = temp;
            }
        }
        // 5、右括号类似处理
        if (right > 0) {
            string temp = curStr;
            curStr += ')';
            right --;
            helper(left, right, curStr, res);
            right ++;
            curStr = temp;
        }
    }
};