难度: Medium
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/
Submission
运行时间: 22 ms
内存: 16.3 MB
from functools import cache
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
@cache
def dfs(n):
if n == 0:
return [""]
res = []
for i in range(n):
left = dfs(i)
right = dfs(n-1-i)
for x in left:
for y in right:
res.append("("+x+")"+y)
return res
return dfs(n)
Explain
这个题解采用了递归加记忆化的方法来生成所有有效的括号组合。基本思路是使用深度优先搜索（DFS），递归地构建每一种可能的括号组合。对于给定的n（括号对数），函数dfs(n)返回所有由n对括号构成的有效组合。递归的基准情况是当n等于0时，只有一个有效的组合，即空字符串。对于n>0的情况，通过枚举左侧括号内包含的括号对数i（从0到n-1），然后对于每个i，计算左侧括号内的组合和右侧的组合，然后将它们组合成一个有效的括号表达式。采用记忆化是为了避免重复计算已经解决的子问题，提高效率。
时间复杂度: O(C_n * n)
空间复杂度: O(C_n * n)
from functools import cache
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
@cache
def dfs(n):
# 基本情况：没有括号对时返回包含空字符串的列表
if n == 0:
return [""]
res = []
# 枚举所有可能的左括号内的括号对数i
for i in range(n):
left = dfs(i) # 左侧i对括号的所有有效组合
right = dfs(n-1-i) # 右侧n-1-i对括号的所有有效组合
# 组合左右两边的结果以形成有效的括号字符串
for x in left:
for y in right:
res.append("("+x+")"+y)
return res
return dfs(n)
Explore
选择枚举左侧括号内包含的括号对数i的原因是为了生成所有可能的有效括号组合。如果每次只简单地添加一对括号，将无法控制和保证括号的正确匹配和组合。通过枚举每个可能的i，我们可以确保左侧和右侧的括号都是有效的，从而构造出所有有效的括号字符串。这种方法可以确保每个生成的字符串都是唯一的有效组合，避免了生成无效或重复的括号组合。
记忆化存储通过存储已经计算的结果来避免重复计算，提高算法的效率。在本题解中，使用了Python的cache装饰器，它自动保存每次函数调用的结果。当递归函数dfs被调用时，cache首先检查是否已经计算过给定参数的结果。如果是，直接返回存储的结果，避免了再次进行相同的计算。这种方法特别适用于递归函数，因为递归过程中很多子问题会被重复计算。通过记忆化，我们可以显著减少计算量，尤其是在处理大量数据时。
Catalan数是一系列自然数，它们在各种计数问题中非常重要，包括括号匹配问题。在括号生成问题中，第n个Catalan数表示n对括号可以形成的不同有效括号组合的数量。算法中使用递归来构造所有有效的括号组合，而Catalan数提供了对组合总数的理论验证。具体来说，Catalan数的递推公式 C(n) = Σ（i=0到n-1）C(i) * C(n-1-i)，与我们在递归算法中使用的括号内外分配方法非常吻合，其中每个C(i)代表左侧i对括号的有效组合数，C(n-1-i)代表右侧对应括号的有效组合数。因此，Catalan数不仅预示了结果的数量，还与算法的结构密切相关。