算法

括号生成

loser

21 Sep 2026 • 5 min read

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

回溯：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path;
        backtrack(n, 0, 0, path, ans);
        return ans;
    }

private:
    void backtrack(int n, int leftCount, int rightCount, string& path, vector<string>& ans) {
        if (path.size() == 2 * n)
        {
            ans.push_back(path);
            return;
        }

        if (leftCount < n)
        {
            path.push_back('(');
            backtrack(n, leftCount + 1, rightCount, path, ans);
            path.pop_back();
        }

        if (rightCount < leftCount)
        {
            path.push_back(')');
            backtrack(n, leftCount, rightCount + 1, path, ans);
            path.pop_back();
        }
    }
};

核心思想

一个有效的括号组合需要满足两个条件：

左括号总数和右括号总数都必须是 n。
从左到右扫描的任意前缀中，右括号数量都不能超过左括号数量。

第二个条件很关键：

右括号数量 <= 左括号数量

如果某个前缀中右括号更多，就说明出现了无法匹配的右括号，后续无论再添加什么字符，都不可能变成有效括号组合。

因此可以使用回溯逐个放置括号，并且只扩展仍然可能合法的状态。

回溯状态

递归函数定义为：

void backtrack(int n, int leftCount, int rightCount, string& path, vector<string>& ans)

其中：

n：需要生成的括号对数。
leftCount：当前路径中已经放置的左括号数量。
rightCount：当前路径中已经放置的右括号数量。
path：当前正在构造的括号字符串。
ans：保存所有完整的有效括号组合。

每一层递归都尝试决定下一个字符放 '(' 还是 ')'。

放置左括号

只要左括号数量还没有达到 n，就可以继续放置左括号：

if (leftCount < n)
{
    path.push_back('(');
    backtrack(n, leftCount + 1, rightCount, path, ans);
    path.pop_back();
}

左括号最多只能出现 n 个，因此条件是：

leftCount < n

放置右括号

右括号不能超过左括号，否则当前前缀就已经无效。

因此只有在：

rightCount < leftCount

时，才可以放置右括号：

if (rightCount < leftCount)
{
    path.push_back(')');
    backtrack(n, leftCount, rightCount + 1, path, ans);
    path.pop_back();
}

这个条件同时保证：

不会出现开头就是 ')' 的非法组合。
不会出现右括号数量超过左括号数量的非法前缀。

为什么不需要单独判断左括号和右括号都达到 `n`

代码只在路径长度达到 2 * n 时记录答案：

if (path.size() == 2 * n)
{
    ans.push_back(path);
    return;
}

每个字符只能是左括号或右括号，路径长度为 2 * n 时，如果左括号数量没有超过 n，右括号数量也没有超过左括号数量，那么两种括号的数量必然都正好是 n。

所以只需要使用路径长度作为终止条件即可。

剪枝

回溯过程中使用了两条剪枝规则：

左括号达到上限

当 leftCount == n 时，不能再放左括号，只能继续放右括号。

右括号不能超过左括号

当 rightCount == leftCount 时，当前所有左括号都还没有被匹配，下一步不能放右括号，只能放左括号。

这两条规则会直接跳过所有不可能形成有效括号组合的分支。

正确性证明

结论 1：算法生成的每个字符串都是有效括号组合

算法只在 leftCount < n 时放置左括号，因此左括号数量不会超过 n。

算法只在 rightCount < leftCount 时放置右括号，因此任意时刻都有：

rightCount <= leftCount

这说明任意前缀中右括号都不会多于左括号，不会出现无法匹配的右括号。

当路径长度达到 2 * n 时，左右括号数量都正好为 n，因此得到的字符串是有效括号组合。

结论 2：所有有效括号组合都会被生成

考虑任意一个有效括号组合：

当它的下一个字符是 '(' 时，由于左括号总数不超过 n，算法允许放置左括号。
当它的下一个字符是 ')' 时，由于组合有效，当前右括号数量一定小于左括号数量，算法允许放置右括号。

因此，任意有效组合中的每一个字符都不会被算法剪枝，算法一定会沿着对应路径生成它。

结论 3：不会生成重复组合

每个递归状态都按照当前路径依次选择下一个括号，每条选择路径唯一对应一个括号字符串。

相同的字符串不可能由两条不同的括号选择路径生成，因此答案中不会出现重复组合。

综上，算法能够生成所有且仅所有有效的括号组合。

示例分析

以 n = 2 为例：

开始：path = ""
放置 '('：path = "("
    放置 '('：path = "(("
        只能放 ')'：path = "(()"
            放置 ')'：path = "(())"
    放置 ')'：path = "()"
        只能放 '('：path = "()("
            放置 ')'：path = "()()"

最终得到：

["(())","()()"]

复杂度分析

设合法括号组合的数量为 C_n，它等于第 n 个卡特兰数：

C_n = 1 / (n + 1) * C(2n, n)

时间复杂度：O(C_n * n)。一共有 C_n 个答案，每个答案长度为 2n，复制并加入结果需要 O(n) 时间。
空间复杂度：O(n)，不计算返回结果。递归深度和当前路径长度最多都是 2n。
若计入返回结果，结果空间复杂度为 O(C_n * n)。

边界情况

n = 1：只能生成 "()"。
左括号数量已经达到 n：后续只能放右括号。
左右括号数量相等：不能继续放右括号，只能放左括号。
任意时刻都不会生成以右括号开头或右括号过多的无效前缀。

回溯：