删除无效括号如何用回溯生成最少删除结果？如何避免重复？

简化版

删除无效括号要求删除最少数量的括号，让结果合法，并返回所有可能结果。

先扫描字符串，计算必须删除的左括号数 leftRemove 和右括号数 rightRemove。

然后回溯每个字符：普通字符必须保留；括号可以选择删除或保留，但保留时要保证当前右括号数量不超过左括号数量。

详细版

这题不能随便删除任意数量括号，因为要求最少删除。

预处理时：

遇到 (，leftRemove++；
遇到 )，如果有未匹配左括号就抵消，否则 rightRemove++。

回溯时维护：

当前下标 index；
剩余可删除左/右括号数；
已保留的左括号数量 leftCount；
已保留的右括号数量 rightCount；
当前路径。

当走到末尾且删除数量用完，并且左右括号数量相等，就加入答案。用 Set 去重。

完整版教学

一、为什么先算最少删除数量

题目要求删除最少括号。如果不先计算必须删除几个左括号和右括号，回溯会枚举大量删除更多字符的结果，最后还要比较长度，复杂且容易错。预处理能告诉我们最少需要删掉多少个 ( 和多少个 )，回溯只在这个预算内搜索。

记忆钩子：最少删除题先算删除预算，再按预算回溯。

二、删除预算怎么计算

从左到右扫描字符串。遇到左括号，暂时记作未匹配；遇到右括号，如果前面有未匹配左括号，就匹配掉一个，否则这个右括号必须删除。

s = "()())"
扫描后 rightRemove = 1, leftRemove = 0
说明至少删 1 个右括号

扫描结束后剩下的未匹配左括号也必须删除。

三、回溯选择有哪些

每个字符有不同处理方式。普通字符不能删，直接加入路径。左括号如果还有删除预算，可以选择删；也可以选择保留，并增加 leftCount。右括号同理，但保留右括号时必须满足 rightCount < leftCount，否则前缀已经非法。

字符	可选动作	额外约束
普通字符	保留	无
`(`	删除或保留	删除需有 `leftRemove`
`)`	删除或保留	保留需不超过左括号

前缀合法性剪枝能大幅减少搜索。

四、代码模板

实现如下：

function removeInvalidParentheses(s) {
  let leftRemove = 0
  let rightRemove = 0
  for (const ch of s) {
    if (ch === '(') leftRemove++
    else if (ch === ')') {
      if (leftRemove > 0) leftRemove--
      else rightRemove++
    }
  }

  const ans = new Set()
  const path = []

  function dfs(index, lr, rr, leftCount, rightCount) {
    if (index === s.length) {
      if (lr === 0 && rr === 0 && leftCount === rightCount) {
        ans.add(path.join(''))
      }
      return
    }
    const ch = s[index]
    if (ch === '(' && lr > 0) dfs(index + 1, lr - 1, rr, leftCount, rightCount)
    if (ch === ')' && rr > 0) dfs(index + 1, lr, rr - 1, leftCount, rightCount)

    if (ch !== '(' && ch !== ')') {
      path.push(ch)
      dfs(index + 1, lr, rr, leftCount, rightCount)
      path.pop()
    } else if (ch === '(') {
      path.push(ch)
      dfs(index + 1, lr, rr, leftCount + 1, rightCount)
      path.pop()
    } else if (rightCount < leftCount) {
      path.push(ch)
      dfs(index + 1, lr, rr, leftCount, rightCount + 1)
      path.pop()
    }
  }

  dfs(0, leftRemove, rightRemove, 0, 0)
  return [...ans]
}

Set 用来处理不同删除位置产生相同字符串的情况。

五、为什么保留右括号要检查前缀合法

合法括号串的任意前缀中，右括号数量都不能超过左括号数量。比如 ")(" 最终左右数量相等，但第一个字符就已经非法，不可能通过后续字符修复这个前缀。因此一旦 rightCount >= leftCount，当前 ) 不能保留。

任意前缀: rightCount <= leftCount
最终整体: rightCount == leftCount

这是括号题最重要的剪枝规则。

六、常见误区与追问

误区：不先算删除预算。 会生成非最少删除结果，还要额外过滤。
误区：只检查最终左右数量相等。 前缀非法的字符串仍可能数量相等，但不是合法括号串。
误区：不用 Set 去重。 删除不同位置的相同括号可能得到同一结果。
追问：能用 BFS 吗？ 可以，按删除层数 BFS，第一次找到合法层就是最少删除。
追问：普通字符能删除吗？ 题目只删除括号，普通字符必须保留。

这些点考的是最少删除、合法前缀和去重。

七、加强记忆

删除无效括号记成“先算预算，再按预算删，保留右括号看前缀”。leftRemove/rightRemove 保证最少删除；普通字符必须保留；右括号只有在已有更多左括号时才能保留。最后删除预算用完且左右数量相等，才加入 Set 去重后的答案。

简化版

详细版