生成有效括号算法问题排查：我的递归回溯JS代码哪里出错？

递归回溯法生成有效括号的核心是严格遵守括号添加规则，以下是这类代码最容易出现的错误点，以及正确的实现参考：

常见错误类型 #

• 括号添加条件逻辑错误
  若错误允许在右括号数量≥左括号时添加右括号，或者左括号未达n就停止添加，会直接生成无效组合或漏掉有效结果。正确逻辑是：

  • 仅当左括号使用数open_bracket < n时，才能添加左括号
  • 仅当右括号使用数close_bracket < open_bracket时，才能添加右括号

• 递归终止条件错误
  若仅用open_bracket === n或close_bracket === n作为终止条件，会生成长度不足2n的不完整括号串。正确终止条件是open_bracket === n && close_bracket === n，此时当前括号组合才是完整有效的。

• 回溯状态未恢复
  添加括号后未执行回溯操作（比如从存储结构中移除最后添加的括号），会导致后续递归的括号串携带之前的残留内容，生成错误组合。

• 结果存储错误
  若直接将存储括号的数组引用存入结果，后续修改会覆盖已保存的结果。正确做法是将数组转为字符串（如ds.join('')）后再存入结果数组。

正确的JS实现示例 #

function generateParenthesis(n) {
    const result = [];
    const backtrack = (ds, open, close) => {
        // 左右括号均用完，保存有效组合
        if (open === n && close === n) {
            result.push(ds.join(''));
            return;
        }
        // 添加左括号的分支
        if (open < n) {
            ds.push('(');
            backtrack(ds, open + 1, close);
            ds.pop(); // 回溯，移除刚添加的左括号
        }
        // 添加右括号的分支
        if (close < open) {
            ds.push(')');
            backtrack(ds, open, close + 1);
            ds.pop(); // 回溯，移除刚添加的右括号
        }
    };
    backtrack([], 0, 0);
    return result;
}

// 测试n=2
console.log(generateParenthesis(2)); // 输出 ["()()", "(())"]

可以对比你的代码，检查是否存在上述错误点，比如是否遗漏了回溯的pop()操作，或者条件判断逻辑不符合规则。

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