括号生成 图解题解

括号生成这道题到底在问什么

给定 n 对括号，要求列出所有「有效」的括号组合。有效的含义是：每个右括号往前看，都能找到一个还没被配对的左括号。注意题目要的是全部方案本身而不是方案个数，所以这是一道枚举型问题——必须把每一个合法串真正构造出来，计数公式帮不上忙。

为什么不先生成所有串再过滤

最直觉的暴力是：把长度 2n 的串每一位都在「(」和「)」里二选一，生成全部 2 的 2n 次方个候选，再逐个检查合法性。n = 3 时就是 64 个候选里挑 5 个，浪费惊人，n 一大更是指数级白干。

关键观察是：一个前缀能不能长成合法串，其实当场就能判定，只取决于两个计数——已放的左括号数 open 和右括号数 close。只要 close 超过 open，或者 open 超过 n，后面无论怎么补都救不回来。既然非法在半路就能看出来，就没必要等整串搭完再验，这正是回溯剪枝的用武之地：边搭边判，非法分支根本不进。

两条落子规则为什么恰好充分又必要

回溯的每一步只问两件事：open < n 吗？是就可以再放一个「(」，因为左括号配额还没用完。close < open 吗？是就可以放一个「)」，因为前面还有落单的左括号等着被配对；若 close 已经追平 open，再放右括号就没有搭档，必然非法。

这两条规则保证了不重不漏。不漏：任何一个合法串，它的每个前缀都天然满足「右括号数不超过左括号数、左括号数不超过 n」，所以这条路径在决策树里一定走得通。不重：每一步先试「(」再试「)」，每个串对应树上唯一一条路径。于是当 len(path) == 2n 时，open 和 close 必然都等于 n，收进结果的一定是完整合法串，连最终校验都省了。

剪枝到底省掉了多少工作量

不剪枝的搜索空间是 2 的 2n 次方，剪枝后真正被展开的路径只有合法串本身加上少量当场夭折的分支。合法串的个数是第 n 个卡塔兰数 C(n) = (2n)! / ((n+1)! n!)，n = 3 时是 5 个：((()))、(()())、(())()、()(())、()()()。每个串长 2n，所以总时间约 O(4ⁿ/√n)——仍是指数，但这是输出规模决定的下限，算法本身没有一点冗余。

复杂度怎么算，哪些写法会翻车

时间约 O(4ⁿ/√n)，由卡塔兰数乘每串长度 2n 得出；空间 O(n)，只有深度 2n 的递归栈和一条 path。最常见的翻车点是把放右括号的条件写成 close < n：这样会放出没有搭档的右括号，产出 )( 这类非法串。另一个细节是收集完必须 return，否则 path 已满还继续往下试，会越界或重复收集。

Python

def generateParenthesis(n):
    res = []
    def bt(path, open, close):
        if len(path) == 2 * n:
            res.append("".join(path)); return
        if open < n:
            bt(path + ["("], open + 1, close)
        if close < open:
            bt(path + [")"], open, close + 1)
    bt([], 0, 0)
    return res

C++

vector<string> res;
void bt(string& p, int open, int close, int n){
    if((int)p.size() == 2*n){ res.push_back(p); return; }
    if(open < n){ p.push_back('('); bt(p,open+1,close,n); p.pop_back(); }
    if(close < open){ p.push_back(')'); bt(p,open,close+1,n); p.pop_back(); }
}
vector<string> generateParenthesis(int n){
    string p; bt(p,0,0,n); return res;
}

Java

List<String> res = new ArrayList<>();
void bt(StringBuilder p, int open, int close, int n){
    if(p.length() == 2*n){ res.add(p.toString()); return; }
    if(open < n){ p.append('('); bt(p,open+1,close,n); p.deleteCharAt(p.length()-1); }
    if(close < open){ p.append(')'); bt(p,open,close+1,n); p.deleteCharAt(p.length()-1); }
}
List<String> generateParenthesis(int n){
    bt(new StringBuilder(), 0, 0, n); return res;
}