22. 括号生成

题目描述

输入整数 n，表示有 n 个 '(' 和 n 个 ')'。

用它们拼成长度为 2n 的字符串，要求括号能完全配对：从左往右扫描时，任何时刻 ')' 的个数都不超过 '(' 的个数。

返回所有符合要求的字符串，顺序不限。

示例 1

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

解释：3 对括号共有 5 种合法组合。

示例 2

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

解释：只有一对括号，唯一的组合是 "()"。

数据范围

1 <= n <= 8

解题思路：计数剪枝回溯

限制左、右括号数量后回溯。

为什么正确

任意前缀都满足右括号数不大于左括号数。

复杂度分析

时间 O(4ⁿ/√n)，额外空间 O(n)。

易错点

注意边界条件并在回溯或弹出后恢复状态。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
 def generateParenthesis(self,n):
  out=[];p=[]
  def f(l,r):
   if l==r==n:out.append(''.join(p));return
   if l<n:p.append('(');f(l+1,r);p.pop()
   if r<l:p.append(')');f(l,r+1);p.pop()
  f(0,0);return out

class Solution {
    List<String> out; StringBuilder p; int n;

    public List<String> generateParenthesis(int n) {
        out = new ArrayList<>(); p = new StringBuilder(); this.n = n;
        f(0, 0); return out;
    }

    void f(int l, int r) {
        if (l == n && r == n) { out.add(p.toString()); return; }
        if (l < n) { p.append('('); f(l + 1, r); p.deleteCharAt(p.length() - 1); }
        if (r < l) { p.append(')'); f(l, r + 1); p.deleteCharAt(p.length() - 1); }
    }
}

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> out; string p;
        function<void(int, int)> f = [&](int l, int r) {
            if (l == n && r == n) { out.push_back(p); return; }
            if (l < n) { p.push_back('('); f(l + 1, r); p.pop_back(); }
            if (r < l) { p.push_back(')'); f(l, r + 1); p.pop_back(); }
        };
        f(0, 0); return out;
    }
};

func generateParenthesis(n int) []string {
    out, p := []string{}, []byte{}
    var f func(l, r int)
    f = func(l, r int) {
        if l == n && r == n {
            out = append(out, string(p))
            return
        }
        if l < n {
            p = append(p, '('); f(l+1, r); p = p[:len(p)-1]
        }
        if r < l {
            p = append(p, ')'); f(l, r+1); p = p[:len(p)-1]
        }
    }
    f(0, 0)
    return out
}

var generateParenthesis = function(n) {
    const out = [], p = [];
    const f = (l, r) => {
        if (l === n && r === n) { out.push(p.join('')); return; }
        if (l < n) { p.push('('); f(l + 1, r); p.pop(); }
        if (r < l) { p.push(')'); f(l, r + 1); p.pop(); }
    };
    f(0, 0); return out;
};

function generateParenthesis(n: number): string[] {
    const out: string[] = [], p: string[] = [];
    const f = (l: number, r: number): void => {
        if (l === n && r === n) { out.push(p.join('')); return; }
        if (l < n) { p.push('('); f(l + 1, r); p.pop(); }
        if (r < l) { p.push(')'); f(l, r + 1); p.pop(); }
    };
    f(0, 0); return out;
};

载入编辑器，自己跑一遍 →

其他解法

暴力枚举先生成再校验，代价是 2²ⁿ；回溯边生成边剪枝，只访问合法前缀；分解法按 (a)b 结构组合子问题，复杂度与回溯同级但要存下中间结果。

解法 2：暴力枚举 + 校验时间 O(2²ⁿ·n)，空间 O(n)

递归生成所有长度为 2n 的括号串，每一位都尝试放 ( 和 )。串长达到 2n 时，从左到右维护余额：遇到 ( 加 1，遇到 ) 减 1。余额从未小于 0 且最终为 0 的串才加入答案。

不需要任何剪枝思路，正确性一目了然。它会生成 2²ⁿ 个串，绝大多数无效；主解法把校验条件提前到放括号的那一刻，只走合法分支。

class Solution:
    def generateParenthesis(self, n):
        out = []
        p = []

        def valid():
            bal = 0
            for ch in p:
                bal += 1 if ch == '(' else -1
                if bal < 0:
                    return False
            return bal == 0

        def f():
            if len(p) == 2 * n:
                if valid():
                    out.append(''.join(p))
                return
            p.append('('); f(); p.pop()
            p.append(')'); f(); p.pop()

        f()
        return out

class Solution {
    List<String> out; StringBuilder p; int n;

    public List<String> generateParenthesis(int n) {
        out = new ArrayList<>(); p = new StringBuilder(); this.n = n;
        f();
        return out;
    }

    boolean valid() {
        int bal = 0;
        for (int i = 0; i < p.length(); i++) {
            bal += p.charAt(i) == '(' ? 1 : -1;
            if (bal < 0) return false;
        }
        return bal == 0;
    }

    void f() {
        if (p.length() == 2 * n) {
            if (valid()) out.add(p.toString());
            return;
        }
        p.append('('); f(); p.deleteCharAt(p.length() - 1);
        p.append(')'); f(); p.deleteCharAt(p.length() - 1);
    }
}

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> out; string p;
        auto valid = [&]() {
            int bal = 0;
            for (char ch : p) {
                bal += ch == '(' ? 1 : -1;
                if (bal < 0) return false;
            }
            return bal == 0;
        };
        function<void()> f = [&]() {
            if ((int)p.size() == 2 * n) {
                if (valid()) out.push_back(p);
                return;
            }
            p.push_back('('); f(); p.pop_back();
            p.push_back(')'); f(); p.pop_back();
        };
        f();
        return out;
    }
};

func generateParenthesis(n int) []string {
    out, p := []string{}, []byte{}
    valid := func() bool {
        bal := 0
        for _, ch := range p {
            if ch == '(' {
                bal++
            } else {
                bal--
            }
            if bal < 0 {
                return false
            }
        }
        return bal == 0
    }
    var f func()
    f = func() {
        if len(p) == 2*n {
            if valid() {
                out = append(out, string(p))
            }
            return
        }
        p = append(p, '('); f(); p = p[:len(p)-1]
        p = append(p, ')'); f(); p = p[:len(p)-1]
    }
    f()
    return out
}

var generateParenthesis = function(n) {
    const out = [], p = [];
    const valid = () => {
        let bal = 0;
        for (const ch of p) {
            bal += ch === '(' ? 1 : -1;
            if (bal < 0) return false;
        }
        return bal === 0;
    };
    const f = () => {
        if (p.length === 2 * n) {
            if (valid()) out.push(p.join(''));
            return;
        }
        p.push('('); f(); p.pop();
        p.push(')'); f(); p.pop();
    };
    f();
    return out;
};

function generateParenthesis(n: number): string[] {
    const out: string[] = [], p: string[] = [];
    const valid = (): boolean => {
        let bal = 0;
        for (const ch of p) {
            bal += ch === '(' ? 1 : -1;
            if (bal < 0) return false;
        }
        return bal === 0;
    };
    const f = (): void => {
        if (p.length === 2 * n) {
            if (valid()) out.push(p.join(''));
            return;
        }
        p.push('('); f(); p.pop();
        p.push(')'); f(); p.pop();
    };
    f();
    return out;
}

解法 3：按首对括号分解时间 O(4ⁿ/√n)，空间 O(4ⁿ/√n)

任何非空合法串都能唯一写成 (a)b，其中 a 含 c 对括号，b 含 n-1-c 对括号，a、b 都合法。gen(k) 枚举 c 从 0 到 k-1，把 gen(c) 与 gen(k-1-c) 的结果两两组合。用哈希表记住每个 k 的结果，gen(0) 只含空串。

直接对应卡特兰数的递推式，适合理解答案个数为什么是卡特兰数。需要保存所有较小规模的结果，内存比回溯大。

class Solution:
    def generateParenthesis(self, n):
        memo = {0: ['']}

        def gen(k):
            if k in memo:
                return memo[k]
            res = []
            for c in range(k):
                for left in gen(c):
                    for right in gen(k - 1 - c):
                        res.append('(' + left + ')' + right)
            memo[k] = res
            return res

        return gen(n)

class Solution {
    Map<Integer, List<String>> memo = new HashMap<>();

    public List<String> generateParenthesis(int n) {
        memo.put(0, new ArrayList<>(List.of("")));
        return gen(n);
    }

    List<String> gen(int k) {
        if (memo.containsKey(k)) return memo.get(k);
        List<String> res = new ArrayList<>();
        for (int c = 0; c < k; c++) {
            for (String left : gen(c)) {
                for (String right : gen(k - 1 - c)) {
                    res.add("(" + left + ")" + right);
                }
            }
        }
        memo.put(k, res);
        return res;
    }
}

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> memo(n + 1);
        vector<bool> done(n + 1, false);
        memo[0] = {""}; done[0] = true;
        function<vector<string>&(int)> gen = [&](int k) -> vector<string>& {
            if (done[k]) return memo[k];
            vector<string> res;
            for (int c = 0; c < k; c++) {
                for (const string& left : gen(c)) {
                    for (const string& right : gen(k - 1 - c)) {
                        res.push_back("(" + left + ")" + right);
                    }
                }
            }
            memo[k] = res; done[k] = true;
            return memo[k];
        };
        return gen(n);
    }
};

func generateParenthesis(n int) []string {
    memo := map[int][]string{0: {""}}
    var gen func(k int) []string
    gen = func(k int) []string {
        if v, ok := memo[k]; ok {
            return v
        }
        res := []string{}
        for c := 0; c < k; c++ {
            for _, left := range gen(c) {
                for _, right := range gen(k - 1 - c) {
                    res = append(res, "("+left+")"+right)
                }
            }
        }
        memo[k] = res
        return res
    }
    return gen(n)
}

var generateParenthesis = function(n) {
    const memo = new Map([[0, ['']]]);
    const gen = (k) => {
        if (memo.has(k)) return memo.get(k);
        const res = [];
        for (let c = 0; c < k; c++) {
            for (const left of gen(c)) {
                for (const right of gen(k - 1 - c)) {
                    res.push('(' + left + ')' + right);
                }
            }
        }
        memo.set(k, res);
        return res;
    };
    return gen(n);
};

function generateParenthesis(n: number): string[] {
    const memo = new Map<number, string[]>([[0, ['']]]);
    const gen = (k: number): string[] => {
        if (memo.has(k)) return memo.get(k)!;
        const res: string[] = [];
        for (let c = 0; c < k; c++) {
            for (const left of gen(c)) {
                for (const right of gen(k - 1 - c)) {
                    res.push('(' + left + ')' + right);
                }
            }
        }
        memo.set(k, res);
        return res;
    };
    return gen(n);
}

回溯专题的其他题目

查看回溯全部题目 →