Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
这题的核心在于如何约束保证最后的结果符合well-formed要求。本质而言如果我们用一个栈模拟,则每次添加一个‘(’,则入栈一个‘)’。栈空则无法加‘)’。否则可以加‘)’。也就是每一步都必须要保证‘(’的数目大于等于‘)’。最后‘(’和‘)’的数目都等于n。用l,r分别表示还需要添加的‘(’和‘)’的数目。代码如下:
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if not n:
return []
cnt = 0 #the number of unadded )
arr = [')','(']
res = []
self.generate([], n, n, res)
return res
def generate(self, cur, l, r, res):
if l > r: #非常关键
return
if l == 0 and r == 0:
res.append(''.join(cur))
return
if l > 0:
cur.append('(')
self.generate(cur, l-1, r, res)
cur.pop()
if r > 0:
cur.append(')')
self.generate(cur, l, r-1, res)
cur.pop()
转载于:https://www.cnblogs.com/sherylwang/p/5764756.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)