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:
[ "((()))", "(()())", "(())()", "()(())", "()()()"]
題目思路：
》尬！①不難發(fā)現(xiàn)，n為0的時候輸出是空，而n = 1的時候主经，輸出“（）”
②當n > 1的時候庭惜，要使得整個括號字符串可以配對罩驻，那么與第一個配對的右括號把n - 1對括號分成了一個 i （0 <= i < n）對已配對的括號和 n - 1 - i對已配對的括號。那么把所有的右括號劃分的情況全部列出來就可以了护赊。由于這里的時間復雜度比較復雜惠遏，就不作分析了砾跃。
根據(jù)上述可以得到：
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
遞歸解法,左括號的個數(shù)比右括號多
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
