22_括号生成

类型：字符串

括号生成 💛

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

❓ 有 n 对括号，生成其所有可能的有效组合。

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

💡 回溯法

我们在枚举的过程中，记录我们目前已经放置的左括号和右括号的数量。在枚举过程中，我们要遵从如下约束：

已放置的左括号的数量小于 n 的时候，我们才可以继续放置左括号。
已放置的右括号数量小于已放置左括号的数量的时候，我们才可以继续放置右括号。

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

        backtrack([], 0, 0)
        return ans

💡 按括号序列的长度递归生成

一个合法的括号表达必然由 ( 开始，并且必然有一个对应的 )，它们中间还可以有括号表达式，它们后面也还可以有括号表达式。因此其形式可以表示为 (a)b，其实 a 和 b 都是合法的括号表达式（可以为空）。

我们的函数 generate(n) 的计算过程如下：

枚举与第一个 ( 对应的 ) 的位置，设为 2 * i + 1
递归调用 generate(i) 即可计算 a 的所有可能性
递归调用 generate(n - i - 1) 即可计算 b 的所有可能性
遍历 a 与 b 的所有可能性并拼接，即可得到所有长度为 2 * n 的括号序列

class Solution:
    @lru_cache(None)
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans