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(使用前将#替换为@)
