题目
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
- 1 <= n <= 8
我的代码（Python）
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
def generateInner(n: int, l: int, r: int, curr: str):
nonlocal result
if n == l:
if n == r:
result.append(curr)
else:
generateInner(n, l, r + 1, curr + ')')
else:
generateInner(n, l + 1, r, curr + '(')
if l > r:
generateInner(n, l, r + 1, curr + ')')
generateInner(n, 0, 0, '')
return result点评
和官方的解法二一致。
根据当前已经生成的括号串内容确定后续动作，如果已经完成就把括号串加入最终结果列表；否则判断能添加哪一个，添加后进入下一轮递归。
考虑过按照括号对数做递归，不过没想太清楚就放弃了，还是直接计算方便。
递归的时间复杂度也差不多，不过是种很好的思路，如果要从底向上计算并缓存就很重要了。
以后题目可以参考。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog