括号生成(回溯)
哪些公司问过
答案要点
- 回溯:维护当前字符串、已用左括号数和右括号数
- 放左括号的条件:左括号数小于 n
- 放右括号的条件:右括号数小于左括号数,保证有效
- 左右括号数都等于 n 时加入结果
- 结果数量是卡特兰数,时间约 O(4^n / √n);注意回溯时恢复现场
易错点
- 先生成所有再校验,没有剪枝
- 放右括号的条件写错,生成无效括号
- 用可变字符串回溯时忘了撤销
面试官常见追问
- 为什么右括号数不能超过左括号数?
- 结果有多少种?
- 还有别的解法吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。