【Leetcode刷题Python】22. 括号生成

1 题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3 输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

输入：n = 1 输出：[“()”]

2 解析

（1）方法一：暴力求解 为了生成所有序列，我们可以使用递归。长度为 nn 的序列就是在长度为 n−1 的序列前加一个 (’ 或 ‘)’。

为了检查序列是否有效，我们遍历这个序列，并使用一个变量balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时balance 的值不为零，那么该序列就是无效的，否则它是有效的。 （2）方法二：回溯方法

如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

3 Python实现

（1）方法一

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:   
        def generate(A):
            if len(A) == 2*n:
                if valid(A):
                    ans.append(''.join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()

        def valid(A):
            bal = 0
            for c in A:
                if c == '(':
                    bal += 1
                else:
                    bal -= 1
                if bal  List[str]:   
		def backtrack(A,left,right):
		            if len(A)==2*n:
		                ans.append(''.join(A))
		                return
		            if left