XingHuiSamaの宝藏之地

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

‍

1. 算法核心思想

本题的要求是生成所有可能的有效括号组合。其核心难点在于：如何在递归过程中实时保证左括号和右括号的排列始终合法。

采用的是回溯算法（Backtracking）。逻辑上，我将生成过程看作是在填补 $2n$ 个空位，每个空位都有放入 ( 或 ) 的决策。为了确保“有效性”，我引入了两个状态变量：

left：当前还剩下多少个左括号可以用。
right：当前还剩下多少个右括号可以用。

核心约束原则：

左括号优先：只要还有左括号剩余，随时可以放左括号。
右括号后置：只有当“已使用的左括号”多于“已使用的右括号”时（对应代码中 left < right），才能放置右括号。
非法拦截：如果剩余左括号数大于剩余右括号数（即 left > right），说明当前的组合中右括号用多了，这绝对不合法，必须提前拦截。

2. 代码逻辑拆解

第一阶段：初始化入口

在 generateParenthesis 主函数中，初始化 left = n 和 right = n，并以空字符串 "" 开启递归探索。
第二阶段：递归终止条件 (Base Case)

当 left == 0 且 right == 0 时，说明 $n$ 对括号已全部配对完成且合法。将当前的 temp 加入结果集 res 并返回。
第三阶段：有效性剪枝 (Pruning)

C++
```
if (left > right) return;
```
这是一个关键的逻辑哨兵。在任何时刻，如果剩余的左括号比右括号还多，意味着在已经生成的路径里，右括号的数量超过了左括号，这违反了有效括号的定义，直接回溯。
第四阶段：决策分叉讨论

我将逻辑细化为三个分支，精准控制递归走向：
- 分支一：left == right
  
  此时必须先放左括号（否则第一位就是右括号，必非法）。
- 分支二：left < right && left > 0
  
  此时既可以尝试放左括号，也可以尝试放右括号。代码在这里产生了两个分身，分别向下探索。
- 分支三：left == 0
  
  此时左括号已用完，剩下的位置只能全部填补右括号。

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 + ")");
        }
    }
};

3. 复杂度分析

时间复杂度：生成括号的有效组合数是一个经典的卡特兰数（Catalan number）问题，第 $n$ 个卡特兰数为 $\frac{1}{n+1}\binom{2n}{n}$ 。其渐进复杂度约为 $O(\frac{4^n}{n\sqrt{n}})$ 。在递归过程中，每个合法组合的构建需要 $O(n)$ 的时间（字符串拷贝），因此整体复杂度较高，但在 $n=8$ 的范围内可以秒过。
空间复杂度： $O(n)$ 。主要开销为递归调用栈的深度，最大深度为 $2n$ 。同时，每层递归创建了临时的字符串变量，其空间占用与 $n$ 成正比。

‍