a 递归

1 括号生成（leetcode 22）

#method1 递归
2n个格子 -- 2^（2n）-- 判断是否合法
#method2 改进（剪枝）
1）局部不合法，不再剪枝
2）左括号只能有n个，右括号只能有n个
class Solution:
    def generateParenthesis(self, n):
        self.list = []
        self._gen(0,0,n,'')
        return self.list
    def _gen(self, left, right, n, result):
        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+')')