【Description】
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
【Idea】
back tracking
从题干分析它的ORT：
T: 假设左右括号对应的剩余数初始为i, j = n, 当i=j=0时，说明当前字符串已经将所有括号都加入且符合条件，加入到指定list；
R: 剩余左括号数一定小于等于剩余右括号数
右括号只有在剩余左括号数小于剩余右括号数时，可以加入；
当剩余左括号大于零时，就可以加入左括号，与右括号状态无关
【Solution】
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
self.generate(n, n, result, '')
return result
def generate(self, left, right, res, string):
if left == 0 and right == 0:
res.append(string)
return
if left < right:
self.generate(left, right-1, res, string + ')')
if left > 0:
self.generate(left-1, right, res, string + '(')
