22. 括号生成

力扣题目链接 (opens new window)

题目描述

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

思路

最直接的想法，是在长度为 2n 的每个位置都尝试放 ( 或 )，最后再判断字符串是否有效。

但这样会生成 2^(2n) 个字符串，大量分支从中途开始就已经不可能合法。例如，第一个字符如果是右括号，无论后面怎么放都救不回来。

能不能在生成过程中就把这些分支剪掉？

我们记录已经使用的左括号数 left 和右括号数 right。一个前缀想要继续成为有效括号串，必须满足两个条件：

1. 左括号最多使用 n 个；
2. 任意时刻右括号数量不能超过左括号数量，即 right < left 时才可以继续放右括号。

为什么第二个条件这么重要？因为右括号只能和前面已经出现的左括号匹配。如果 right > left，当前前缀已经无效，后面再补左括号也不能改变这个事实。

回溯不是把所有情况都枚举完，而是一旦确定某条路不可能得到答案，就立刻回头。

回溯三部曲：

1. 递归参数：当前字符串、左右括号已经使用的数量；
2. 终止条件：字符串长度达到 2n，收集答案；
3. 单层逻辑：左括号没用完就放左括号；右括号少于左括号才放右括号。

模拟过程

以 n = 3 为例，从空字符串开始。左分支尝试放 (，右分支只有在前缀仍然合法时才会出现。

沿着最左侧分支会先得到 ((()))。回溯到上一个选择点后，再尝试 (()())、(())() 等分支。像 )(、()) 这样的前缀不会进入搜索树，因为它们出现了右括号多于左括号的情况。

解题代码

class Solution {
private:
    vector<string> result;

    void backtracking(int n, int left, int right, string& path) {
        if (path.size() == 2 * n) {
            result.push_back(path);
            return;
        }

        if (left < n) {
            path.push_back('(');
            backtracking(n, left + 1, right, path);
            path.pop_back();
        }

        if (right < left) { // 右括号只能匹配已经出现的左括号
            path.push_back(')');
            backtracking(n, left, right + 1, path);
            path.pop_back();
        }
    }

public:
    vector<string> generateParenthesis(int n) {
        string path;
        backtracking(n, 0, 0, path);
        return result;
    }
};

复杂度分析

• 时间复杂度：O(Cn × n)，其中 Cn 是第 n 个卡特兰数；共有 Cn 个答案，复制每个长度为 2n 的字符串需要 O(n)。
• 空间复杂度：O(n)，递归深度和当前路径长度均为 O(n)，不计返回结果。

其他语言

Python3

class Solution:
    def generateParenthesis(self, n: int):
        result, path = [], []

        def backtracking(left, right):
            if len(path) == 2 * n:
                result.append("".join(path))
                return
            if left < n:
                path.append("(")
                backtracking(left + 1, right)
                path.pop()
            if right < left:
                path.append(")")
                backtracking(left, right + 1)
                path.pop()

        backtracking(0, 0)
        return result

Java

class Solution {
    private final List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        backtracking(n, 0, 0, new StringBuilder());
        return result;
    }

    private void backtracking(int n, int left, int right, StringBuilder path) {
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }
        if (left < n) {
            path.append('(');
            backtracking(n, left + 1, right, path);
            path.deleteCharAt(path.length() - 1);
        }
        if (right < left) {
            path.append(')');
            backtracking(n, left, right + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

Go

func generateParenthesis(n int) []string {
    result, path := []string{}, []byte{}
    var backtracking func(int, int)
    backtracking = func(left, right int) {
        if len(path) == 2*n {
            result = append(result, string(path))
            return
        }
        if left < n {
            path = append(path, '(')
            backtracking(left+1, right)
            path = path[:len(path)-1]
        }
        if right < left {
            path = append(path, ')')
            backtracking(left, right+1)
            path = path[:len(path)-1]
        }
    }
    backtracking(0, 0)
    return result
}

JS

var generateParenthesis = function(n) {
    const result = [];

    function backtracking(path, left, right) {
        if (path.length === 2 * n) {
            result.push(path);
            return;
        }
        if (left < n) backtracking(path + "(", left + 1, right);
        if (right < left) backtracking(path + ")", left, right + 1);
    }

    backtracking("", 0, 0);
    return result;
};

与代码随想录联系

本题就是回溯算法中的树形搜索。建议先掌握回溯算法理论基础，再对比77.组合。

组合问题用 startIndex 控制下一层从哪里开始，本题则用 left 和 right 控制哪些分支还能继续。参数不同，选择、递归、回溯的框架完全一致。