有效括号生成回溯实现疑问：递归为何能枚举所有合法组合

你在调试监视窗口看到的right值自动下降，本质是递归栈帧切换带来的显示效果差异，全程不存在对同一个right变量的主动修改。

Python中的整数属于不可变对象，递归调用时传递的是参数值的副本：每一次调用backtrack函数，系统都会为这次调用在独立的栈内存块中创建专属的left、right、S、ans局部变量，和外层函数的同名下变量没有任何引用绑定。

举个N=2场景下的栈帧切换实例：

• 当你走到第一组合法括号"(())"的递归最深层时，当前栈帧的right=2，此时递归执行完return语句，调试器会自动把显示切回上一层早已存在的栈帧——这层栈帧在创建时传入的right参数就是1，所以你会看到监视窗口的right值从2跳回1。这个值从始至终没有被修改过，只是调试器的显示视角从最深的栈位置上移到了外层的栈帧而已。

这段递归逻辑的核心是带合法性剪枝的全路径遍历，两个if判断就是遍历过程中的两个固定决策方向，只要满足规则就不会跳过分支，自然能覆盖所有合法组合：

• if left < N：只要左括号的使用数量没到总配额N，就优先尝试在当前路径末尾追加左括号，保证所有序列都从合法的左括号起点展开
• if right < left：只要当前右括号数量少于左括号数量，就尝试在当前路径末尾追加右括号，从根源上避免出现右括号多余、整体失配的非法序列

结合N=2的实际遍历路径就能看清代码如何跳出第一组组合、探索后续结果：

1. 从空串出发，因为left=0<2，优先走“加左括号”分支，进入S='('的路径
2. 在S='('路径，再次满足left<2条件，走“加左括号”分支，进入S='(('的路径
3. 在S='(('路径，left已经达到配额2，无法再追加左括号，触发right<left条件，先后两次追加右括号，生成第一组结果"(())"存入答案数组
4. 等S='(('这条分支的所有决策全部执行完毕，递归自动回退到S='('的外层栈帧：这层栈帧中“加左括号”的分支已经探索完成，现在轮到第二个判断条件生效——right=0 < left=1，所以会触发全新的递归调用，走“加右括号”的分支，此时S为"()"
5. 在S="()"的路径中，left=1<2满足加左括号条件，进入S='()('的路径，此时right=1 < left=2，追加右括号就生成第二组结果"()()"存入答案数组

整个过程没有人为中断分支遍历的逻辑，所有满足合法性要求的路径都会被依次探索、记录，最终就能收集到全部符合规则的括号组合。

内容的提问来源于stack exchange，提问作者Rohan J. Dani