22.括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

分析

左右括号匹配成对才能合法。

方法

思路一：数学归纳法 O(2^n)
n=1 （）
n=2 (()),()()
n=3 …

思路二：递归/深度优先搜索 O（2^2n）
知道n,就知道合法的字符串长度 为2n
在2n 长度内每个位置都有两种可能 所以整个的candidate 是2^2n 列举出所有可能，最后判断是否合法即可。

思路三：方法二的改进 进行剪枝O(2^n)
（1）局部不合法，不再递归，上来直接是右括号。
（2）每次记得左括号用了多少,右括号用了多少。用过一次记一次。

代码实现

class Solution(object):
	def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.list = []
        self._gen(0,0,n,'')
    
    def _gen(self,left,right,n,result):   # left ,right 表示已经用了多少个
        if left ==n and right ==n:
            self.list.append(result)
            return
        if left < n:
            self._gen(left +1,right,n,result+'(')
        if left > right and right < n:
            self._gen(left,right+1,n,result+')')

TIPS

代码风格小tips :
（1）if 后最好有空格
（2）{ 之前也最好有空格,且不要另起一行
（3）缩进最好是2个空格，并非4个空格
（4）递归终止条件最好可以先列出来
python coding style goole