.jpg)
577 字
3 分钟
括号生成
.png)
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
解题思路
- 回溯算法框架：
- 递归构建括号组合，实时跟踪左右括号数量
- 当前字符串长度达2n时保存结果
- 剪枝策略：
- 左括号数 < n 时可添加左括号
- 右括号数 < 左括号数时可添加右括号
- 平衡约束：
- 始终保持右括号数 ≤ 左括号数
- 最终左右括号数相等
- 路径记录：
- 传递当前组合字符串
- 完成时加入结果集
关键洞察
- 括号有效性原理：
- 任意前缀中左括号数 ≥ 右括号数
- 结束时左括号数 = 右括号数 = n
- 状态传递机制：
- 左右括号计数决定可选操作
- 避免无效分支扩展
- 卡特兰数特性：
- 解的数量是卡特兰数 Cₙ
- 时间复杂度由卡特兰数决定
- 深度优先优势：
- 自然实现组合构造
- 剪枝大幅减少无效搜索
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 优势 |
|---|---|---|---|
| 回溯法 | O(4ⁿ/√n) | O(n) | 直观易理解 |
| BFS | O(4ⁿ/√n) | O(4ⁿ/√n) | 避免递归栈溢出 |
| DP | O(4ⁿ/√n) | O(4ⁿ/√n) | 适合多次调用 |
代码实现
回溯
/** * @param {number} n * @return {string[]} */var generateParenthesis = function (n) { if (n === 1) return ['()']; const res = []; const dfs = (l, r, s) => { if (s.length === 2 * n) { res.push(s) return; } if (l > 0) { dfs(l - 1, r, s + '(') } if (r > l) { dfs(l, r - 1, s + ')') } } dfs(n, n, '') return res;};DP
const generateParenthesis= (n) => { const dp = [['']]; // dp[0] = ['']
for (let i = 1; i <= n; i++) { dp[i] = []; for (let j = 0; j < i; j++) { for (const left of dp[j]) { for (const right of dp[i - 1 - j]) { dp[i].push(`(${left})${right}`); } } } } return dp[n];};实际应用场景
- 代码编译器：自动生成所有可能的括号匹配测试用例`
- 数学组合问题：计算卡特兰数具体实例`
- DNA序列生成：生物信息学中RNA二级结构预测`
- 游戏关卡设计：解谜游戏中括号匹配关卡生成`