22. 括号生成

https://leetcode-cn.com/problems/generate-parentheses/

解法一：暴力

先生成所有括号的组合，然后逐个检测是否满足条件。

重点是生成所有的组合（长度为2*n，每个位置有左括号和右括号两种可能，共2^2n种情况），用递归。

检测是否符合就比较简单了，看左右是否配对即可。注意避免右括号先于左括号出现的情况

还有就是python的函数内定义嵌套函数，调用不用加self，引用外层参数也不用

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:    
        def generate(A):    #回溯生成函数
            if len(A) == 2*n:    #递归出口
                if valid(A):    #调用验证
                    res.append(''.join(A))
                return
            #经典回溯
            A.append('(')
            generate(A)
            A.pop()
            A.append(')')
            generate(A)
            A.pop()
        
        def valid(A):    #验证函数
            bal = 0    #balance，遇到左括号+1，右括号-1
            for ch in A:
                if ch == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False    #若右括号先出现
            return bal == 0
        
        res = []
        generate([])
        return res

简化写法：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A):
            if len(A) == 2*n:
                if (valid(A)):
                    res.append(''.join(A))
                return
            #简洁回溯
            generate(A + ['('])
            generate(A + [')'])

        def valid(A):    #验证函数
            bal = 0    #balance，遇到左括号+1，右括号-1
            for ch in A:
                if ch == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False    #若右括号先出现
            return bal == 0
        
        res = []
        generate([])
        return res

将generate函数中参数A由list改为字符串，更加直接：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A):
            if len(A) == 2*n:
                if (valid(A)):
                    res.append(A)
                return
            generate(A + '(')
            generate(A + ')')
            
        def valid(A):    #验证函数
            bal = 0    #balance，遇到左括号+1，右括号-1
            for ch in A:
                if ch == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False    #若右括号先出现
            return bal == 0
        
        res = []
        generate('')
        return res

解法二：回溯

不是先生成所有组合，而是生成所有合法的组合

用left，right表示左右括号数，先加左括号，保证左括号数=n；然后加右括号，保证右括号数=左括号，递归回溯。这在回溯过程中保证左右括号相等，而不是解法一中生成最终组合后才判断左右是否相等，因此速度更快

注意左右递归的两个if是并列的，而不能是二选一的if else。如果二选一，就变成一直递归左括号直到n，再递归右括号，最终只生成一个结果

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:    
        def generate(A, left, right):
            if len(A) == 2*n:    #出口
                res.append(''.join(A))
                return
            if left < n:    #先加左括号
                #经典回溯格式
                A.append('(')
                generate(A, left+1, right)
                A.pop()
            if right < left:    #若右括号不足，补充右括号
                A.append(')')
                generate(A, left, right+1)
                A.pop()
        res = []
        generate([], 0, 0)
        return res

也可以换种写法，将新A直接写入递归函数中，这样每次递归的A都保存在当前层次的递归函数中，不需要再append，pop操作。78.子集的回溯也可以如此改写

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:    
        def generate(A, left, right):
            if len(A) == 2*n:
                res.append(''.join(A))
                return
            if left < n:
                generate(A+['('], left+1, right)                
            if right < left:
                generate(A+[')'], left, right+1)
        res = []
        generate([], 0, 0)
        return res

简化：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A, left, right):
            if len(A) == 2*n:
                res.append(A)
                return
            if left < n:
                generate(A + '(', left+1, right)
            if right < left:
                generate(A + ')', left, right+1)

        res = []
        generate('', 0, 0)
        return res