一、括号生成

1、问题

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

2、思路

任何一个括号序列都一定是由 " ( " 开头，并且第一个 " ( " 一定有一个唯一与之对应的 )。这样一来，我们只需要考虑 i=n 时相比 i=n-1 时 “增加的那一组括号” 的位置是“添加在括号里面”、还是“添加在括号外面”。

每一个括号序列可以用 “( p ) q” 来表示，其中 p 与 q 分别是一个合法的括号序列（也可以为空）。

• dp[i] 表示 i 组括号的所有有效组合
• dp[i] = “( 【dp[p] 的所有有效组合】) +【dp[q] 的所有有效组合】”，其中 1 + p + q = i , p 从 0 遍历到 i-1 , q 则相应从 i-1 到 0

3、代码

#coding：utf-8
from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [[] for _ in range(n + 1)]  # dp[i]存放i组括号的所有有效组合
        dp[0] = [""]  # 初始化dp[0]
        for i in range(1, n + 1):  # 计算dp[i]
            for p in range(i):  # 遍历p
                l1 = dp[p]  # 得到dp[p]的所有有效组合
                l2 = dp[i - 1 - p]  # 得到dp[q]的所有有效组合
                for k1 in l1:
                    for k2 in l2:
                        dp[i].append("({0}){1}".format(k1, k2))

        return dp[n]


if __name__ == "__main__":
    n = 3
    s = Solution()
    print(s.generateParenthesis(n))

4、时间与空间复杂度

时间复杂度：

O

(

4

n

n

)

O( /dfrac{4^n }{/sqrt{n}} )

O(n
​4n​)

空间复杂度：

O

(

4

n

n

)

O( /dfrac{4^n }{/sqrt{n}} )

O(n
​4n​)

备注

1、“问题”转载于：
力扣（LeetCode）

2、参考：
【最简单易懂的】动态规划

分享到：

赞(0) 打赏