题目描述：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
我的方法：
一种思路是列出所有可能性，排除其中不合法的组合。这种方法的时间复杂度高达O()。这自然不是一种经济的方法。
如果仔细考察结果，我们能够发现合法的结果符合以下特征：
- 最左边一定是左括号“（”，最右边的一定是右括号“）”。
- 都是由3个左括号、3个右括号构成。
- 也许可以用递归，合法字符串剔除两个最内层的括号之后，剩余的部分依然合法。
- 每个合法字符串必然至少有一对最内层的括号，当然也可以有嵌套的括号。
最终是使用递归方法来处理的。正如之前所述，递归需要考虑移动和终止条件两个因素。
中文网站居然报错（而且显然是网站自身问题导致的报错），只好去leetcode英文网站来提交了。效果一般，但总算没有超时。Runtime: 88 ms, faster than 5.64% of Python online submissions for Generate Parentheses.Memory Usage: 12.2 MB, less than 5.02% of Python online submissions for Generate Parentheses.
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n==1:
return ["()"]
# n对括号可以认为是n-1和1对括号的组合
# 其中这1对括号可以看成是一个整体，同时移动
ans=[]
for ele in self.generateParenthesis(n-1):
for i,v in enumerate(ele):
tmp=ele[:i]+'()'+ele[i:]
if tmp not in ans:
ans.append(tmp)
return ans
别人的方法：
用的是回溯，这个方法算是新技能，直观上不太容易理解。回溯就是通过不同的尝试来生成问题的解。有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思是对已知错误的结果没必要再继续尝试了。
回溯的步骤如下：
- 定义合法的搜索结果：左括号的数量等于n，并且右括号的数量等于n。凡是合法的搜索结果，便加入到数组ans中。
- 定义括号生成的路径，也可以理解成是树生成的路径。只有在两种情况下，才可能生成合法的树。
- 一种生长路径是：左括号的数量l小于n时，可以对字符串s增加左括号，每次增加一个左括号。
- 另一种生长路径是：当左括号的数量l>右括号数量r时，可以对字符串s增加右括号，每次增加一个右括号。
- 通过递归调用，这两种生长路径可能会相互以不同的顺序穿插，从而生成不同的合法字符串s。
效果有所提升：执行用时 : 36 ms, 在Generate Parentheses的Python提交中击败了33.55% 的用户。内存消耗 : 12.2 MB, 在Generate Parentheses的Python提交中击败了0.00% 的用户
class Solution(object):
def generateParenthesis(self, N):
res=[]
def backtrack(s,n,l,r):
if l==n and r==n:
res.append(s)
return
if l<n:
# 注意：这里是调用，而无需返回。
# 每一次调用，都可能生成合法结果
backtrack(s+'(',n,l+1,r)
if l>r:
backtrack(s+')',n,l,r+1)
# 注意backtrack()并不返回任何值，只是改变了变量res的值
backtrack('',N,0,0)
# 最终输出res即可
return res
