括号生成
Generate Parentheses
本机进度仅保存在当前浏览器
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：n = 3，输出 ["((()))", "(()())", "(())()", "()(())", "()()()"]。
解题思路
- 把"合法"翻译成可执行的剪枝条件：任意前缀中左括号数不少于右括号数，且最终两者相等。
- 维护已用左括号数 l 与右括号数 r：l < n 时可以放左括号，r < l 时可以放右括号，其他分支全部剪掉。
- 路径长度达到 2n 即收集；剪枝保证生成的每个前缀都合法，无需事后校验。
参考实现
查看参考实现Python · 建议先自行作答
def generateParenthesis(n):
res, path = [], []
def backtrack(l, r):
if len(path) == 2 * n:
res.append(''.join(path))
return
if l < n:
path.append('(')
backtrack(l + 1, r)
path.pop()
if r < l:
path.append(')')
backtrack(l, r + 1)
path.pop()
backtrack(0, 0)
return res