难度: Medium
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1 输出:["()"]
提示:
1 <= n <= 8
难度: Medium
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1 输出:["()"]
提示:
1 <= n <= 8
运行时间: 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
该题解使用回溯法生成有效的括号组合。通过递归的方式,不断地尝试添加左括号和右括号,同时使用一个栈来记录当前未匹配的左括号数量。在递归过程中,根据栈的大小和已生成的括号数量,选择添加左括号或右括号。当生成的括号数量达到 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 ```
在生成有效括号的过程中,栈用来记录未匹配的左括号。如果栈为空,意味着没有未匹配的左括号,因此只能添加左括号。如果栈的大小已达到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,此时必须添加右括号来匹配已有的左括号。这种处理确保每一步操作都符合有效括号序列的要求,即在任何时刻,添加右括号的数量不能超过左括号的数量。