22. 括号生成

难度：🟡 Medium | 标签：回溯 | 状态：⬜ LeetCode 链接

思路

DFS 维护当前左右括号数：

• 左 < n：可加左
• 右 < 左：可加右

到达 2n 长度收集。

代码

class Solution {
    vector<string> res;
    string path;
    int n_;
    void dfs(int open, int close) {
        if ((int)path.size() == 2 * n_) { res.push_back(path); return; }
        if (open < n_) {
            path.push_back('(');
            dfs(open + 1, close);
            path.pop_back();
        }
        if (close < open) {
            path.push_back(')');
            dfs(open, close + 1);
            path.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        n_ = n;
        dfs(0, 0);
        return res;
    }
};

复杂度

• 时间 O(卡特兰数 C(n))
• 空间 O(n)

易错 / 回顾

• 「右 < 左」保证合法性——任何前缀左括号数都 ≥ 右括号数
• 不要尝试列所有 2² 组合再筛——大量无效路径