题目描述
思路解析
一句话答案：把每个字符串看成搜索状态：第 d 层表示恰好删除 d 个括号。BFS 第一次出现合法字符串的层就是最少删除层；检查完整层并收集所有合法状态，再停止向下扩展，才能同时保证‘删除最少’和‘结果不漏’。
这题不是只求一个合法字符串
LeetCode 301 要求删除最少数量的无效括号，并返回这个最少删除数下的所有不同结果。比如 `()())()` 只需删除一个右括号，但有 `(())()` 和 `()()()` 两个答案，返回任意一个都不完整。
两遍贪心可以在线性时间构造一个最少删除的合法串，适合 LC1249；它无法枚举同样少删的所有不同结果，因此不能作为 LC301 的完整主解。
为什么分层 BFS 天然保证删除最少
把原字符串放在第 0 层。从某个状态删除一个左括号或右括号，就得到下一层状态。因此第 d 层中的每个字符串都恰好删除了 d 个括号。
BFS 按 0、1、2……的顺序检查删除次数。只要前面各层都没有合法串，而第 d 层第一次出现合法串，就能直接证明最少删除数是 d；更深层都会删除更多，没有继续搜索的价值。
怎样在线性时间验证一个候选
用 balance 记录当前尚未匹配的左括号数：遇到 `(` 加一，遇到 `)` 减一，字母跳过。如果扫描途中 balance 变成负数，说明当前右括号左侧没有可匹配的左括号，候选立即无效。
扫描结束时 balance 还必须等于 0。大于 0 表示仍有左括号没有右括号配对。于是一个候选的验证时间是 O(n)，而且字母会原样保留。
为什么要去重，而且要检查完整个命中层
删除相邻的相同括号经常得到同一个字符串。例如从连续的两个右括号中删除任意一个，结果可能完全相同。每层使用集合保存状态，能避免重复入队、重复验证和重复输出。
在某一层找到第一个合法串时不能立刻返回。同层其他状态删除的括号数量完全相同，也可能是最优答案。正确停止方式是：检查完整个当前层，收集本层所有合法串；若集合非空，就返回它们，并且不再生成下一层。
正确性可以拆成最少性与完整性
最少性来自 BFS 层序：首次命中层之前的所有较少删除方案已经被完整验证，均不合法；首次命中层之后的状态删除更多，不可能更优。
完整性来自扩展规则与整层收集：每个状态都尝试删除每一个括号，所以所有删除 d 个括号的候选都会被覆盖；集合只合并内容相同的状态，不会丢掉不同结果；首次命中层又会被完整扫描，因此该层所有不同的合法串都会进入答案。
复杂度、边界与 DFS 替代方案
括号的删除子集最坏可达指数数量，每个候选还需 O(n) 验证或构造，所以时间复杂度最坏为 O(n·2^n)，空间最坏为 O(2^n)。BFS 的价值是最少性直观，并通过按层停止避免搜索更深状态，不是把指数问题变成多项式。
原串已经合法时，第 0 层直接返回它；`)(` 这类输入最终返回空串；纯字母串原样返回。也可以先统计必须删除的左右括号数，再用 DFS 加剩余字符剪枝枚举答案，通常更省层集合空间，但正确性仍要同时说明最少和不漏。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
BFS 的层数天然等于删除次数：先检查少删的层，再检查多删的层，因此第一次命中的层一定最优。
队列不是逐个乱搜，而是按层处理。第 0 层只有原串 `()())()`，先判断它是否合法。
合法性有两道门：扫描途中不能出现多余右括号，扫描结束也不能剩下未配对左括号。
先扫描 `()`：左括号把 balance 加到 1，紧跟的右括号把它降回 0；当前前缀合法，但还不能提前判断整串合法。
扫描到 `()()` 时 balance 再次归零。下一字符还是右括号，它左边已经没有待配对的左括号。
第 5 个字符让 balance 变成 -1。后面再出现左括号也救不了这个已经缺少左括号的前缀，因此候选立即判无效。
合法性不是只看最后 balance=0：途中出现过负数已经非法；同时结束时还必须恰好归零。
原串在第二个连续右括号处失衡，所以 0 次删除无解。现在才允许生成删除 1 个括号的候选。
每个子状态只删除一枚括号。先删除开头左括号，得到 `)())()`；它以右括号开头，稍后会很快判无效。
继续枚举两个不同位置：(())() 会成为答案，()))() 则会在扫描中失衡；此时还不能跳过任何未枚举位置。
删除相邻的两个右括号会产生同一个 `()()()`。visited 按字符串内容去重，避免重复验证和重复输出。
最后两个删除位置生成 `()()))` 与 `()())(`。到这里第 1 层候选才算完整，下一步才能整层验证。
只删除括号，字母绝不能删。相邻的相同括号可能生成同一字符串，所以候选必须去重。
两个相邻右括号分别删除会得到同一个 `()()()`；集合把它们合并成一个状态。
先验证前两个候选：`)())()` 立刻失败，`(())()` 全程配平，记入答案，但仍不能提前返回。
第三个候选 `()))()` 无效。已经有一个答案也必须继续，因为同层剩余状态删除次数同样最少。
第四个候选 `()()()` 合法，加入答案集合。现在已有两个不同最优结果，但仍要把本层剩余状态检查完。
最后两个候选都无效。至此第 1 层完整检查结束，答案集合恰好是 `(())()` 与 `()()()`。
本层出现了两个合法串。注意不能看到第一个就返回，否则会漏掉同样只删一个括号的另一个答案。
第一批合法串出现在删除 1 次这一层，已证明 0 次无解。更深层都会多删，所以停止搜索。
两遍贪心可以解决只返回一个结果的 LC1249，但不能替代本题“返回所有最优结果”的搜索。
已合法输入、全无效括号、纯字母和重复状态，分别检验第 0 层返回、空串语义和去重。
面试回答要明确区分 LC301 与 LC1249，并能说明 BFS 和计数剪枝 DFS 的取舍。
参考代码
class Solution: def removeInvalidParentheses(self, s): def valid(text): balance = 0 for ch in text: if ch == '(': balance += 1 elif ch == ')': balance -= 1 if balance < 0: return False return balance == 0 level = {s} while level: answer = [text for text in level if valid(text)] if answer: return answer next_level = set() for text in level: for i, ch in enumerate(text): if ch in '()': next_level.add(text[:i] + text[i + 1:]) level = next_level return ['']复杂度
- 时间：最坏 O(n·2^n)，括号子集状态可能指数级，每个候选验证或构造需 O(n)
- 空间：最坏 O(2^n)，集合保存一层的去重候选；输出本身也可能很多