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:
[ "((()))", "(()())", "(())()", "()(())", "()()()"]
题目思路：
①不难发现，n为0的时候输出是空，而n = 1的时候，输出“（）”
②当n > 1的时候，要使得整个括号字符串可以配对，那么与第一个配对的右括号把n - 1对括号分成了一个 i （0 <= i < n）对已配对的括号和 n - 1 - i对已配对的括号。那么把所有的右括号划分的情况全部列出来就可以了。由于这里的时间复杂度比较复杂，就不作分析了。
根据上述可以得到：
f(n) = ∑( '(' + f(i) +')' + f(n - 1 - i) )
class Solution(object):
"""
:type n: int
:rtype: List[str]
"""
def generateParenthesis(self, n):
result = []
def func(left,right,s):
if left < right :
return
if (left+right == n*2):
if (left == right):
result.append(s)
return
func(left,right+1,s+')')
func(left+1,right,s+'(')
func(1,0,'(')
return result
递归解法,左括号的个数比右括号多
class Solution(object):
"""
:type n: int
:rtype: List[str]
"""
def generateParenthesis(self, n):
result = []
def func(left,right,s):
if left < right :
return
if (left+right == n*2):
if (left == right):
result.append(s)
return
func(left,right+1,s+')')
func(left+1,right,s+'(')
func(1,0,'(')
return result
