生成有效括号代码出现重复结果的原因及代码差异分析

核心问题根源 #

你得到重复结果的本质是：回溯过程中存在多条不同的递归路径生成了完全相同的括号字符串，而标准的有效括号回溯逻辑会通过严格的条件限制，确保每个合法组合只被生成一次。

常见错误场景及对比 #

对比标准回溯逻辑，你的代码大概率在以下某一点出现了偏差：

1. 未正确限制右括号的添加条件
   标准逻辑中，只有当已使用的右括号数量 < 已使用的左括号数量时，才允许添加右括号。如果你的代码缺失这个限制，或者错误地使用了剩余括号数量的判断（比如逻辑写反），会导致同一字符串被不同路径重复生成。

2. 递归触发了重复的选择分支
   比如在同一递归层级中，你可能重复调用了添加左括号/右括号的递归函数。举个例子：错误代码可能在某个条件下，既执行了backtrack(s + '(', left-1, right)，又在另一个相同条件下再次执行了相同的调用，导致同一分支被遍历两次，最终生成重复结果。

3. 未正确维护递归状态的唯一性
   如果你的代码在回溯时，没有正确传递或更新左/右括号的剩余数量（比如不小心复用了同一个变量引用），导致不同递归分支的状态相互干扰，也可能生成重复的结果。

示例对比（标准逻辑vs错误逻辑） #

标准回溯代码逻辑（确保无重复）：

def generateParenthesis(n):
    res = []
    def backtrack(s, left, right):
        if len(s) == 2 * n:
            res.append(s)
            return
        if left < n:
            backtrack(s + '(', left + 1, right)
        if right < left:
            backtrack(s + ')', left, right + 1)
    backtrack('', 0, 0)
    return res

如果你的代码中，比如把第二个条件写成right < n而不是right < left，或者在某个地方重复调用了backtrack，就会导致重复生成相同的字符串。比如当left=1, right=1时，错误地允许再次添加右括号，后续路径会和其他分支生成相同的组合。

排查建议 #

• 打印递归过程中的每一步s、left、right值，观察是否有不同的(left, right)组合生成了相同的s。
• 对比标准逻辑的条件判断，检查你的代码中左/右括号的添加条件是否严格符合：
  • 左括号：已使用数量 < n（或剩余数量 > 0）
  • 右括号：已使用数量 < 已使用左括号数量（或剩余右括号 > 剩余左括号）

内容的提问来源于stack exchange，提问作者luke liang