括号生成

难度: Medium

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

Submission

运行时间: 52 ms

内存: 15.1 MB

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        def backtrack(path, stack):
            if len(path) == 2 * n and len(stack) == 0:
                ans.append(''.join(path))

            if len(path) >= 2 * n:
                return

            if len(stack) > n:
                choices = [")"]
            elif len(stack) == 0:
                choices = ["("]
            else:
                choices = ["(", ")"]

            for choice in choices:
                path.append(choice)
                if choice == '(':
                    stack.append('(')
                else:
                    stack.pop()
                backtrack(path, stack)
                path.pop()
                if choice == '(':
                    stack.pop()
                else:
                    stack.append('(')

        backtrack([], [])
        return ans

Explain

该题解使用回溯法生成有效的括号组合。通过递归的方式，不断地尝试添加左括号和右括号，同时使用一个栈来记录当前未匹配的左括号数量。在递归过程中，根据栈的大小和已生成的括号数量，选择添加左括号或右括号。当生成的括号数量达到 2*n，且栈为空时，说明生成了一个有效的括号组合，将其加入结果列表中。

时间复杂度: O((4^n) / (n^(1/2)))

空间复杂度: O((4^n) / (n^(1/2)))

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        
        def backtrack(path, stack):
            # 如果生成的括号数量达到 2*n，且栈为空（所有左括号都已匹配），则将当前路径加入结果列表
            if len(path) == 2 * n and len(stack) == 0:
                ans.append(''.join(path))
            
            # 如果生成的括号数量超过 2*n，则不继续递归
            if len(path) >= 2 * n:
                return
            
            # 根据栈的大小选择下一个括号的类型
            if len(stack) > n:
                choices = [")"]  # 如果栈的大小超过 n，则只能添加右括号
            elif len(stack) == 0:
                choices = ["("]  # 如果栈为空，则只能添加左括号
            else:
                choices = ["(", ")"]  # 否则可以添加左括号或右括号
            
            # 对每个可选的括号类型进行递归
            for choice in choices:
                path.append(choice)
                if choice == '(':
                    stack.append('(')  # 如果添加左括号，将其入栈
                else:
                    stack.pop()  # 如果添加右括号，将栈顶的左括号出栈
                backtrack(path, stack)
                path.pop()  # 回溯，移除当前添加的括号
                if choice == '(':
                    stack.pop()  # 回溯，将之前入栈的左括号出栈
                else:
                    stack.append('(')  # 回溯，将之前出栈的左括号重新入栈
        
        backtrack([], [])
        return ans
```

Explore

在生成有效括号的过程中，栈用来记录未匹配的左括号。如果栈为空，意味着没有未匹配的左括号，因此只能添加左括号。如果栈的大小已达到n，表示左括号已经用完，此时只能添加右括号以匹配已存在的左括号。栈的大小实际上反映了当前左括号和右括号的添加状态，决定了下一步可以安全添加的括号类型，以保证括号序列的有效性。

卡特兰数是一种重要的组合数学公式，用于解决各种在结构和数量上受限的组合问题。有效括号的问题可以用卡特兰数计算，因为每个有效的括号组合必须满足左括号数量等于右括号数量，并且在任意前缀中左括号数量不少于右括号数量。第n个卡特兰数是：C(n) = 1/(n+1) * (2n choose n)，它准确地计算了n对括号能形成的有效组合数量。

递归函数`backtrack`通过试探性地添加左括号或右括号并递归，检查生成的括号组合是否有效。在每次递归调用后，需要撤销之前的操作（添加的括号），确保每个可能的括号位置都可以正确尝试所有的选项。对于栈操作，添加左括号时入栈，撤销时相应地出栈，以保持栈状态正确反映未匹配的左括号数量，这是确保生成所有有效组合的关键步骤。

该检查确保当生成的括号数量达到最大（即2*n个，n对左括号和n对右括号）时停止添加新括号，这是因为进一步的添加会导致括号数量超过要求，破坏括号组合的有效性。当`len(path) == 2 * n`且栈为空时，表示已生成一个完整的有效括号组合。

考虑n=3的情况，生成的有效括号组合数（卡特兰数）是5。每个组合的生成涉及到6个字符的添加过程。时间复杂度主要由生成各个组合的过程决定，即C(3)次完整的递归流程，每个流程中的操作次数与n成线性关系，因此时间复杂度为O((4^n) / (n^(1/2)))。空间复杂度包括递归调用栈空间和结果存储空间，对于每个递归调用，栈的最大深度为2n，而存储所有结果的空间取决于组合数和每个组合的长度，故空间复杂度为O(C(n) * n)，即O((4^n) / (n^(1/2)))。

栈大小为0表示没有未匹配的左括号，因此只能添加左括号。栈大小超过n时，意味着左括号的数量已达到最大值n，此时必须添加右括号来匹配已有的左括号。这种处理确保每一步操作都符合有效括号序列的要求，即在任何时刻，添加右括号的数量不能超过左括号的数量。