分類：String
考察知識點：String/BackTracking
最優(yōu)解時間復雜度：O(n!)~O(2^n)(如果沒有l(wèi)eft>right的限制條件)
最優(yōu)解空間復雜度：O(n)
22. Generate Parentheses
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
代碼：
我的方法:
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res=[]
if n==0:
return res
def doGenerate(res,s,left,right):
if left>right:
return
if left==0 and right==0:
res.append(s)
return
if left>0:
doGenerate(res,s+"(",left-1,right)
if right>0:
doGenerate(res,s+")",left,right-1)
doGenerate(res,"",n,n)
return res
討論：
1.這道題是一道典型BackTracking的題棘伴，是最最常見的攒巍，也是最最基礎的
2.left>right這個細節(jié)茵休，是因為比如n=5,left=3,right=2的時候,那么之前的s就會是“(()))”，這就說明之前的那個情況是不匹配的
3.卡特蘭數(shù)是一種題目可以使用分治的思想但是有所限制的時候，那么就會使用到比如在（0,n-1）的時候电抚，再到(1,n-2).....(n-1,0)一層層的，都可以使用這個思想解決問題
典型BackTracking題拳魁！加油乘客！
