给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
s=''
res=[]
left=right=n
self.helper(s, res, left, right)
return res
# 二叉树的广度优先?
def helper(self,s,res,left,right):
'''
:param s: str
:param res: List[str]
:param left: int64
:param right: int64
:return: list
'''
# 空节点暂停遍历
if left==0 and right==0:
res.append(s)
# 遍历左子树。条件:左括号剩余可添加个数>0。
if left>0:
self.helper(s+'(',res,left-1,right)
# 遍历右子树。
# 添加了一个左括号才能添加右括号。所以right>left。
if right>left:
self.helper(s+')',res,left,right-1)
网友评论