22.括号生成
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
思路
1.暴力法
可以生成所有 2^2n 个 ‘(‘ 和 ‘)’ 字符构成的序列，然后我们检查每一个是否有效即可。
2.回溯法
方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 ‘(‘ or ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
3.按括号序列的长度递归
代码
from functools import lru_cache
class Solution(object):
def generateParenthesis(self, n):
"""
暴力法
:type n: int
:rtype: List[str]
"""
# 生成所有括号组合，然后判断是否是有效括号
def generate(A):
if len(A) == 2 * n:
# print(A)
if valid(A):
ans.append("".join(A))
else:
A.append('(')
generate(A)
A.pop()
A.append(')')
generate(A)
A.pop()
def valid(A):
bal = 0 # 表示左括号的数量减去右括号的数量
for c in A:
if c == '(':
bal += 1
else:
bal -= 1
if bal < 0:
return False
return bal == 0
ans = []
generate([])
return ans
def generateParenthesis1(self, n):
"""
回溯法
对暴力解法的改进：
只在序列仍然保持有效时才添加 '(' or ')'，而不是像 暴力解法 那样每次添加
我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点
如果左括号数量不大于 n，我们可以放一个左括号
如果右括号数量小于左括号的数量，我们可以放一个右括号
"""
def backtrack(S, left, right):
if len(S) == 2 * n:
ans.append(''.join(S))
return
if left < n:
S.append('(')
backtrack(S, left + 1, right)
S.pop()
if right < left:
S.append(')')
backtrack(S, left, right + 1)
S.pop()
ans = []
backtrack([], 0, 0)
return ans
class Solution1:
@lru_cache(None)
def generateParenthesis(self, n: int):
"""按括号序列的长度递归"""
if n == 0:
return ['']
ans = []
for c in range(n):
for left in self.generateParenthesis(c):
for right in self.generateParenthesis(n-1-c):
ans.append('({}){}'.format(left, right))
return ans
if __name__ == '__main__':
slt = Solution1()
parenthesis_list = slt.generateParenthesis(3)
print(parenthesis_list)