22. 括号生成 Medium

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

示例 1:
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2:
输入：n = 1
输出：["()"]

解题思路

输入：一个整数 n，表示要生成 n 对括号

输出：返回所有可能的、合法的括号组合

这道题属于子集型回溯问题。

回溯三问

1. 当前操作？

   • 在当前位置 i（表示当前构造的括号长度）：
     • 如果左括号 ( 数量 open_count 还没有达到 n，可以放一个左括号。
     • 如果右括号 ) 数量（i - open_count）小于左括号数量 open_count，可以放一个右括号，保证括号合法性。
   • 每次尝试一种可能的选择，并将当前选择放入 path 中。

2. 子问题？

   • 放置了一个括号后，需要继续递归处理下一个位置（即 i+1），同时更新左括号数量（对于 (）或者右括号数量（间接通过 i - open_count 计算）。
   • 继续放置剩余的括号，直到构造完整个括号串。

3. 下一个子问题？

   • 当当前位置 i 继续选择放置 ( 或 ) 时，就形成了二叉分支。
   • 继续递归，直到路径长度等于 2 * n 时，将合法的组合加入到结果列表 ans 中。

剪枝条件

• 如果左括号数量大于 n，直接剪枝（非法）。
• 如果右括号数量大于左括号数量，直接剪枝（非法）。

代码实现

python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []  # 用于存放所有合法的括号组合
        path = []  # 用于存放当前括号组合的构造路径

        def dfs(i: int, open_count: int):
            """
            i：当前处理的字符位置
            open_count：当前使用的左括号数量
            """
            if i == 2 * n:
                # 当构造的括号长度达到 2 * n 时，说明找到了一个合法组合
                ans.append(''.join(path))
                return
            
            # 1. 选择左括号
            if open_count < n:
                path.append('(')
                dfs(i + 1, open_count + 1)
                path.pop()  # 回溯

            # 2. 选择右括号
            # 右括号数量不能超过左括号数量（即必须保证合法性）
            close_count = i - open_count
            if close_count < open_count:
                path.append(')')
                dfs(i + 1, open_count)
                path.pop()  # 回溯

        # 从位置 0 开始递归，初始时左括号数量为 0
        dfs(0, 0)
        return ans

javascript

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const ans = [];
    const path = [];

    function dfs(i, open) {
        if (i == 2 * n) {
            ans.push(path.join(''));
            return;
        }

        if (open < n) {
            path.push('(');
            dfs(i + 1, open + 1);
            path.pop();
        }

        if (i - open < open) {
            path.push(')');
            dfs(i + 1, open);
            path.pop();
        }
    }

    dfs(0, 0);
    return ans;
};

复杂度分析

时间复杂度：O(4^n)

空间复杂度：O(n * 4^n)

链接

22 国际版

22 中文版