括号生成(LeetCode 22)的回溯解法
哪些公司问过
答案要点
- 回溯时记录当前串、已用左括号数和右括号数
- 左括号数小于 n 时可加左括号
- 右括号数小于左括号数时才可加右括号,保证前缀合法
- 左右括号数都等于 n 时收集结果
- 结果数为卡特兰数,n=3 时共 5 种
易错点
- 加右括号的条件写成 right < n,会产生非法前缀
- 用字符串拼接时不注意回溯撤销
- 把结果数量误认为 2^n 或 n!
面试官常见追问
- 除了回溯还有别的思路吗?
- 如果先生成所有 2^(2n) 个串再判断合法性,有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。