137/300

22. 括号生成
    给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
     
    例如，给出 n = 3，生成结果为：
     
    [
    “((()))”,
    “(()())”,
    “(())()”,
    “()(())”,
    “()()()”
    ]
     
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/generate-parentheses

思路一： 插

例：n = 2
第一步：n= 1： ‘()’
第二步：n = 2:
‘()‘ 插 ’()‘ ： ‘()’[0:0] +'()' +’()’[0:2] = '()()'
                     ‘()’[0:1] +'()' +’()’[1:2] = '(())'

例：n = 3
第一步：n= 1： ‘()’
第二步：n = 2: 如上得到 ‘()()’ ，’(())’
第三步：
‘()()’ 插 ‘()’ ： ‘()()’[0:0] +'()' +’()()’[0:4] = '()()()'
                              ‘()()’[0:1] +'()' +’()()’[1:4] = '(())()'
                              ‘()()’[0:2] +'()' +’()()’[2:4] = '()()()'
                              ‘()()’[0:3] +'()' +’()()’[3:4] = '()(())'

‘(())’ 插 ‘()’ ： ‘(())’[0:0] +'()' +’(())’[0:4] = '()(())'
                              ‘(())’[0:1] +'()' +’(())’[1:4] = '(()())'
                              ‘(())’[0:2] +'()' +’(())’[2:4] = '((()))'
                              ‘(())’[0:3] +'()' +’(())’[3:4] = '(()())'

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if not n: return []
        
        res = set()
        res.add('()')
        
        for i in range(n-1):
        
            tmp = set()
            for p in res:
            
                n = len(p)
                for j in range(n):

                    tmp.add(p[0:j]+'()'+p[j:n])
           
            res = tmp
        return list(res)

思路二：

recursion 正向生成

条件1：左括号没到n个，加左边
条件2：左括号没到n个，左边括弧比右边多，补右边
条件3：左括号等于n个，右括号补全了，这个就要了

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        
        def generate(p, l, r):
            
            if l <= n : 		  generate(p +'(', l+1 ,r)
            if l <= n and l > r : generate(p +')', l , r+1) 
            if l == n and r == n: res.append(p)
            
        generate('',0, 0)    
        return res

recursion 反向生成

例：n = 3， 3个"(" + 3个")"
左括号仨备用，右括号仨备用
左括号有备用：用掉一个左括号，’(’，剩下左括号俩备用，右括号仨备用
左括号有备用：用掉一个左括号，’((’， 剩下左括号一备用，右括号仨备用
左括号有备用：用掉一个左括号，’(((’， 剩下左括号无备用，右括号仨备用
左括号无备用，右括号比左括号多：用掉一个右括号，’((()’，剩下右括号俩备用
左括号无备用，右括号比左括号多：用掉一个右括号，’((())’，剩下右括号一备用
左括号无备用，右括号比左括号多：用掉一个右括号，’((()))’，剩下右括号无备用
右括号无备用，添加'((()))'
恢复右括号一个，'((())'，剩下右括号一备用
恢复右括号一个，'((()'，剩下右括号俩备用
恢复右括号一个，'((('，右括号仨备用
恢复左括号一个，'(('，剩下左括号一备用，右括号仨备用
左括号有备用，右括号比左括号多：用掉一个右括号，’(()’，剩下左括号一备用，右括号俩备用
左括号有备用：用掉一个左括号，’(()(’，剩下右括号俩备用
左括号无备用，右括号比左括号多：用掉一个右括号，’(()()’，剩下右括号一备用
左括号无备用，右括号比左括号多：用掉一个右括号，’(()())’，剩下右括号无备用
右括号无备用，添加'(()())'
以此类推…

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        
        def generate(p, l, r):
            
            if l:     generate(p + '(', l-1, r)    
            if l < r: generate(p + ')', l, r-1)
            if not r: res.append(p)
                
        generate('', n, n)
        return res