题干
22. 括号生成
难度中等980收藏分享切换为英文关注反馈
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路一（突发奇想）
我刚做这道题的时候，思路比较清奇，做出来之后评论区大概没有人有这种想法，可以提供一个新的思路
对于当前长度为m的括号串，在字符之间有m+1个空隙，而每个空隙中插入一个‘()’都有可能组成一个新的括号串，
这样当已经有一个括号个数为k的括号串的时候，通过这种方式就能得出括号数为k+1的括号串。
当然这种方法会产生较多重复情况，需要进行排除，并且时空开销并不优秀。
- Pyhon代码
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
self.ansSet = set({})
self.generateByN('', n)
return list(self.ansSet)
def generateByN(self, cur, n):
if n == 0:
self.ansSet.add(cur)
return
for i in range(len(cur) + 1):
array = list(cur)
array.insert(i, '()')
self.generateByN(''.join(array), n - 1)
执行结果：通过
执行用时 :2004 ms, 在所有 Python3 提交中击败了5.58%的用户
内存消耗 :13.9 MB, 在所有 Python3 提交中击败了6.06%的用户
最终看到时间开销确实也不低，但是可以稍作优化。
-
稍作优化
优化主要是在循环找插入点的时候，提前进行去重，这样时间上可以优化不少
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
self.ansSet = set({})
self.generateByN('', n)
return list(self.ansSet)
def generateByN(self, cur, n):
if n == 0:
self.ansSet.add(cur)
return
curSet = set({})
for i in range(len(cur) + 1):
array = list(cur)
array.insert(i, '()')
curSet.add(''.join(array))
for newCur in curSet:
self.generateByN(newCur, n - 1)
执行结果：通过
执行用时 :332 ms, 在所有 Python3 提交中击败了5.58%的用户
内存消耗 :13.8 MB, 在所有 Python3 提交中击败了6.06%的用户
可以看到，时间上优化了不少，但是不得不承认，这种方法并不优秀，但是可以起到一个拓展思路的作用。
思路二（动态规划）
这种思路的核心思想就是：
长的括号串可以由短的括号串拼接或者外套括号组成，
短的括号串可以由更短的括号串拼接或者外套括号组成，
这样递归下来，最终所有的括号串都会追溯到n=1的括号串，简化问题。
若要计算n个括号的括号串,以下用dp[k] 表示k个括号组成的有效括号串集合
首先定义dp[1] = ['()']
之后计算dp[2],dp[3]....dp[n]
以下为计算dp[k]的过程：
第1组操作：
分别从dp[1]和dp[k - 1]中取出一个括号串，将其拼接即可得到长度为k的括号串，并计算所有可能的组合
将dp[1]中每个字符串左右各加k-1层单括号
第2组操作
分别从dp[2]和dp[k - 2]中取出一个括号串，将其拼接即可得到长度为k的括号串，并计算所有可能的组合
将dp[2]中每个字符串左右各加k - 2层单括号
···
···
···
第k-1组操作
分别从dp[k - 1]和dp[1]中取出一个括号串，将其拼接即可得到长度为k的括号串，并计算所有可能的组合
将dp[k - 1]中每个字符串左右各加1层单括号
由于整个过程是对称的，所以每次对两个字符串进行拼接时只考虑 左+右 一种方式即可
- Python代码
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
dpMap = {1: ['()']}
for num in range(2, n + 1):
ansSet = set()
for half in range(1, num):
ansSet = ansSet|{left + right for left in dpMap[half] for right in dpMap[num - half]}
ansSet = ansSet|{'(' * half + item + ')'*half for item in dpMap[num - half]}
dpMap[num] = list(ansSet)
return dpMap[n]
执行结果：通过
执行用时 :44 ms, 在所有 Python3 提交中击败了58.40%的用户
内存消耗 :14.2 MB, 在所有 Python3 提交中击败了6.06%的用户
