Problem
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
Algorithmic thinking
如果您有两个堆栈，一个用于n“（”，另一个用于n“）”，则从这两个左/右括号堆栈生成二叉树以形成输出字符串。
这意味着无论何时进行更深入的遍历，都会从其中一个堆栈中弹出一个括号。当两个堆栈为空时，您将形成一个输出字符串。
如何形成合法的字符串？这是一个简单的观察：
对于输出字符串是正确的，“）”的堆栈大于“（”的堆栈。如果不是，它创建类似“（）”的字符串“由于每个堆栈中的元素是相同的，我们可以简单地用数字表示它们。例如，left = 3就像一个堆栈[“（”，“（”，“（”]
Python3 Solution1
class Solution:
def generateParenthesis(self, n: int) -> list:
if not n:
return []
left, right, ans = n, n, []
self.helper(left, right, '', ans)
return ans
def helper(self, left, right, item, res):
if left:
self.helper(left-1, right, item+'(', res)
if right > left:
self.helper(left, right-1, item+')', res)
if not left and not right:
res.append(item)
return
Python3 Solution2
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
dp = [[] for _ in range(n + 1)]
dp[0].append('')
for i in range(n + 1):
for j in range(i):
dp[i] += ['(' + x + ')' + y for x in dp[j] for y in dp[i - j - 1]]
return dp[n]
