Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, givenn= 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
这道题目非常符合动态规划的的方法，所以我们这里采用该方法进行解题，先把左边括号加到底，然后右括号加到底。然后逐渐往回退只要是符合左右括号都为零就符合要求
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res_ = []
self.dfs(n,n,'',res)
return res
def dfs(self,left,right,s,res):
if left == 0 and right == 0:
res.append(s)
else:
if left > 0:
self.dfs(left-1,right,s+'(',res)
if right > left:
self.dfs(left,right-1,s+')',res)
