22. 括号生成

题目描述

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

思路

尝试把问题缩减为子问题。

如果现在有了 n 对括号，那么我们想生成 n+1 对括号的话，需要把括号放在哪里呢？

尝试从 0 开始枚举：

• 0: []
• 1: [()]

对于两对括号的情况，它要么包裹第一对括号，要么放在第一对括号的外面：

• 2: [(()),()()]

那么考虑有多种括号的情况呢？

我们其实可以将括号分成三个部分：假设一共有 n 个括号，我们想新添加一个括号，将剩下 n-1 个括号分成 p 和 q，并且我们有一个 dp[i] 的数组，保存了从 0 到 n-1 的括号组合。

那么我们 dp[n] 的元素一定是 ({e_p}){e_q}，其中 e_p 和 e_q 是 dp[p] 和 dp[q] 中的元素。

那么这样我们就可以一层一层地构造 dp 数组，最后返回 dp[n]。

最终代码：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [[""]]
        for i in range(1, n+1):
            dpi = []
            for p in range(0, i):
                q = i-1-p
                for ep in dp[p]:
                    for eq in dp[q]:
                        dpi.append("({}){}".format(ep, eq))
            dp.append(dpi)
        return dp[n]

想得太多

• p 的范围处理的有点问题，因为 python 右边界取不到 i，因此 p 的最大值就是 i-1。因此 range 边界不需要设置为 i-1。
• 为什么只有 ({e_p}){e_q} 一种情况呢？感觉可以用反证法证明。