Leetcode——括号生成

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        int left = n;   // 剩余可用左括号
        int right = n;  // 剩余可用右括号
        vector<string> result;
        func(result, left, right, "");
        return result;
    }

    void func(vector<string> &res, int left, int right, string temp) {
        // 1. 递归终点：左右括号全部用完
        if (left  0 && right  0) {
            res.push_back(temp);
            return;
        }

        // 2. 剪枝：如果剩余左括号多于右括号，说明此时路径中右括号多于左括号，非法
        if (left > right) {
            return;
        }

        // 3. 情况一：左右括号剩余数量相等，必须放左括号
        if (left  right) {
            func(res, left - 1, right, temp + "(");
        }

        // 4. 情况二：左括号少于右括号且还有左括号，可放左也可放右
        if (left < right && left > 0) {
            // 尝试放左括号
            func(res, left - 1, right, temp + "(");
            // 尝试放右括号
            func(res, left, right - 1, temp + ")");
        }

        // 5. 情况三：左括号用完，只能放右括号
        if (left  0) {
            func(res, left, right - 1, temp + ")");
        }
    }
};

‍