leetcode22.括号生成

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解答

• 递归解法

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result; // 用于存储最终结果的向量

        // 调用递归函数开始生成括号
        generate(result, "", 0, 0, n);

        return result;
    }

private:
    // 递归生成括号的辅助函数
    void generate(vector<string>& result, string current, int open, int close, int max) {
        // 当前生成的括号串长度等于2 * n时，将其加入结果向量
        if (current.length() == 2 * max) {
            result.push_back(current);
            return;
        }

        // 如果左括号的数量小于n，可以添加左括号
        if (open < max) {
            generate(result, current + "(", open + 1, close, max);
        }

        // 如果右括号的数量小于左括号，可以添加右括号
        if (close < open) {
            generate(result, current + ")", open, close + 1, max);
        }
    }
};