分类：String
考察知识点：String/BackTracking
最优解时间复杂度：O(n!)~O(2^n)(如果没有left>right的限制条件)
最优解空间复杂度：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这个细节，是因为比如n=5,left=3,right=2的时候,那么之前的s就会是“(()))”，这就说明之前的那个情况是不匹配的
3.卡特兰数是一种题目可以使用分治的思想但是有所限制的时候，那么就会使用到比如在（0,n-1）的时候，再到(1,n-2).....(n-1,0)一层层的，都可以使用这个思想解决问题
典型BackTracking题！加油！
