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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
[ "((()))",
"(()())",
"(())()",
"()(())",
"()()()"]
()
/ \
() ()
/ \ / \
() ()()()
"""
ans = []
path = []
self.gen_par_helper(n*2, path, ans)
return ans def is_valid_par(self, par):
stack = []
for c in par:
if c == "(":
stack.append("(")
else:
if stack:
stack.pop()
else:
return False
return len(stack) == 0 def gen_par_helper(self, n, path, ans):
if n == 0:
if self.is_valid_par(path):
ans.append("".join(path))
return
for c in "()":
path.append(c)
self.gen_par_helper(n-1, path, ans)
path.pop()
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
[ "((()))",
"(()())",
"(())()",
"()(())",
"()()()"]
()
/ \
() ()
/ \ / \
() ()()()
"""
ans = []
self.gen_par_helper(n, n, "", ans)
return ans def gen_par_helper(self, left, right, path, ans):
if left == 0 and right == 0:
ans.append(path)
return
if left > 0:
self.gen_par_helper(left-1, right, path+"(", ans)
if right > 0 and right > left:
self.gen_par_helper(left, right-1, path+")", ans)
第二种更快，只是不那么容易想到！