刷题刷到中后期，判断一道题有没有嚼头，我习惯先看它能不能一句话问懵人。"删除无效的括号"就是这么一道题：看起来只是把字符串里多余的括号删掉，但真要动手写，才发现必须回答三个问题——删几个、删哪些、重复结果怎么办。这道题在各类算法题库里都非常经典，也是面试环节的常客，它表面考回溯，实际考的是对括号匹配本质的理解程度。这篇题解我会用 Python 把这道题拆开讲透：先用计数器算清最少要删多少括号，再讲 DFS 回溯如何枚举所有方案，最后补充 BFS 版本和几处很容易翻车的边界细节。
1. 括号问题的底层规律：合法括号串不能只靠"数量相等"
很多人拿到这道题的第一反应是：统计字符串里左右括号的数量，哪边多就删哪边，删到一样多不就合法了吗？这个思路对了一半，但如果真按这个逻辑写，会挂在下面这个例子上。
1.1 一个反直觉的例子：")((" 左右括号数量相等，却完全非法
先看字符串")(("。它有两个右括号？不对，准确说是")("这个例子更典型，但我们可以用一个更极端的：")(("有两个左括号一个右括号？我重新选个干净的例子，")("。左右括号各一个，数量相等，但显然不合法，因为第一个字符就是右括号，它没法和任何左侧的左括号配对。
再比如"))(("，左右各两个，数量完全相等，但整个串里没有一对合法括号。这类字符串的存在说明，括号合法性的判定条件和"数量相等"是两回事。
1.2 判定合法只需要一个计数器
判断一个括号串是否合法，不需要栈，也不需要正则，一个整数计数器就够了。我从左往右扫描整个字符串，维护一个变量balance，规则只有两条：
- 遇到左括号
(，balance += 1； - 遇到右括号
)，balance -= 1；如果减完之后balance < 0，立刻判定非法。
扫描结束后，balance必须恰好等于 0，这个字符串才合法。
这个规则背后的直觉很生活化：把左括号想象成欠条，右括号想象成还款。你可以在任何时刻持有欠条（balance 为正），但绝不能在没欠条的时候还款（balance 变成负数）。扫描结束还欠着钱（balance 为正）也不行，因为字符串已经结束了，没人再给你还款机会。
所以"删除无效的括号"这道题，本质上就是在保证balance全程不为负、最终为 0 的前提下，用最少的删除次数改造原串。理解了这个计数器逻辑，后面所有的解法都建立在这条规则之上。
2. 先算"最少删几个"：预扫描给出删除配额
暴力做法是枚举所有子序列，再逐个判断合法性。但s最长能有 25 个字符，子序列数量是 2 的 25 次方，也就是三千多万，每个还要做一次线性合法性校验，Python 直接跑会非常吃力。
所以正确姿势是先做一次预处理，算出"最少必须删除的左括号数"和"最少必须删除的右括号数"，把问题从"删多少个"缩小为"删哪几个"。
2.1 预扫描规则与手算演示
我用两个变量lrem和rrem分别记录需要删除的左括号数、右括号数，从左往右扫描原串：
- 遇到左括号，
lrem += 1，意思是"当前有一个左括号等待被匹配"； - 遇到右括号，先看
lrem是否大于 0。如果大于 0，说明这个右括号能匹配掉前面一个还没配对的左括号，让lrem -= 1；如果lrem已经是 0，说明这个右括号前面没有可匹配的左括号，它本身是多余的，必须删掉，所以rrem += 1。
扫描结束后，lrem里剩下的就是"到末尾都没被匹配掉的左括号"，也是必须删除的；rrem就是必须删除的右括号。
拿题目给的示例s = "()())()"走一遍：
| 字符 | 操作前 lrem | 操作前 rrem | 操作后 lrem | 操作后 rrem |
|---|---|---|---|---|
| ( | 0 | 0 | 1 | 0 |
| ) | 1 | 0 | 0 | 0 |
| ( | 0 | 0 | 1 | 0 |
| ) | 1 | 0 | 0 | 0 |
| ) | 0 | 0 | 0 | 1 |
| ( | 0 | 1 | 1 | 1 |
| ) | 1 | 1 | 0 | 1 |
结果lrem = 0，rrem = 1。也就是说，这个字符串只需要删除 1 个右括号就能变合法，这和题目的预期输出完全对得上：["(())()", "()()()"]都是删除一个右括号后的结果。
2.2 为什么最优解必然刚好删掉这些配额
这个预扫描为什么可信？因为它是贪心的。它对每个右括号做的是"能匹配就匹配"，这意味着所有能被正常匹配的括号都消耗掉了，剩下的左括号和右括号本质上就是结构性冗余。
关键结论是：任何一组"删除最少数量括号后合法"的解，删掉的左括号数量必然等于lrem，删掉的右括号数量必然等于rrem。理由很简单——预扫描找出的这些括号是必须删的，因为不删它们就不可能让 balance 归零且不为负；而如果删了别的括号，删除总数就会超过最小值。所以最优解恰好拥有固定的删除配额，我们后面枚举的只是"配额内部的分配方案"。
2.3 配额如何变成剪枝条件
有了配额，递归时的剪枝条件就很清晰了：在当前分支里，如果已经删除的左括号数超过lrem，或者删除的右括号数超过rrem，这个分支就已经偏离最优解，直接终止。这一步能把大量无效分支提前掐死，是 DFS 版本性能的关键。
3. DFS 主解：逐字符决策 + 剪枝 + 去重
预处理拿到删除配额后，核心问题就变成：从字符串的每个位置开始，决定这个字符是保留还是删除。因为我们已经知道最多删多少个括号，所以这不是无边无际的搜索，而是在一个很小的解空间里找所有方案。
3.1 递归的状态设计与转移条件
我设计递归函数时，每个参数都要有意义：
pos：当前扫描到原串s的哪个位置；cur：已经构造出来的前缀字符串；balance：当前前缀里未匹配的左括号数量；lrem/rrem：剩余还能删除的左括号数、右括号数。
每来到一个字符，只有三种情况：
- 当前字符是普通字母：普通字母不在删除范围内，直接保留，
cur后追加这个字母，其他状态不变。 - 当前字符是左括号：要么保留（
balance + 1），要么删除（lrem - 1）。 - 当前字符是右括号：要么删除（
rrem - 1），要么保留。但保留右括号有一个前提条件：当前balance必须大于 0。因为如果前面没有未匹配的左括号，这个右括号一保留，balance 立刻变负数，后续就算把整个字符串走完也不可能修复了。
这个"保留右括号前检查 balance"的剪枝，是整棵树能不能瘦身的关键。没有它，递归会在大量注定非法的分支里白跑。
递归终止条件：pos扫描完了，同时balance == 0，且lrem == 0且rrem == 0，这个cur就是一个合法答案。
3.2 完整 Python 实现
from typing import List class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: # 第一次扫描：统计最少需要删除的左、右括号数量 lrem = rrem = 0 for ch in s: if ch == '(': lrem += 1 elif ch == ')': if lrem > 0: lrem -= 1 else: rrem += 1 ans = [] visited = set() n = len(s) def dfs(pos: int, cur: str, balance: int, lrem: int, rrem: int) -> None: if balance < 0 or lrem < 0 or rrem < 0: return key = (pos, cur, balance, lrem, rrem) if key in visited: return visited.add(key) if pos == n: if balance == 0 and lrem == 0 and rrem == 0: ans.append(cur) return ch = s[pos] if ch == '(': # 删掉这个左括号 if lrem > 0: dfs(pos + 1, cur, balance, lrem - 1, rrem) # 保留这个左括号 dfs(pos + 1, cur + ch, balance + 1, lrem, rrem) elif ch == ')': # 删掉这个右括号 if rrem > 0: dfs(pos + 1, cur, balance, lrem, rrem - 1) # 保留右括号：前面必须有未匹配的左括号 if balance > 0: dfs(pos + 1, cur + ch, balance - 1, lrem, rrem) else: # 普通字母只能保留 dfs(pos + 1, cur + ch, balance, lrem, rrem) dfs(0, "", 0, lrem, rrem) return ans这份代码直接提交就能通过。它在每个位置都走"删"和"不删"两条路，但因为配额和 balance 的双重剪枝，实际展开的分支数远小于 2 的 N 次方。
3.3 为什么需要 visited 去重
如果字符串里有多个连续的相同括号，比如"((a"，删除第一个左括号和删除第二个左括号，最终得到的都是"(a"。DFS 会把这两条不同路径都走到尽头，产生同一个结果。
我没用"最后对结果去重"这种偷懒方案，而是在状态层面去重。只要(pos, cur, balance, lrem, rrem)完全一致，后续无论怎么走都等价，只搜一次就够了。这个细节对性能影响非常大，尤其当输入里有连续重复括号序列时，能省下很多重复分支。
4. BFS 备选方案：按层删除的直观思路
DFS 是"先算配额再搜索"，BFS 则是另一种完全不同的思路：从原串开始，每一层尝试删除一个括号，生成所有可能的新字符串，直到这一层出现了合法字符串。因为 BFS 是按"删除次数"一层层扩展的，所以第一次遇到合法串的那一层，就是最少删除次数。
4.1 BFS 版本 Python 实现
from collections import deque from typing import List class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: def is_valid(x: str) -> bool: balance = 0 for ch in x: if ch == '(': balance += 1 elif ch == ')': balance -= 1 if balance < 0: return False return balance == 0 visited = {s} q = deque([s]) ans = [] found = False while q: cur = q.popleft() if is_valid(cur): ans.append(cur) found = True continue if found: # 已经找到最少删除次数的结果，不再继续生成更短的串 continue for i, ch in enumerate(cur): if ch not in "()": continue nxt = cur[:i] + cur[i + 1:] if nxt not in visited: visited.add(nxt) q.append(nxt) return ans这里有个容易写错的地方：found = True之后，当前队列里可能还有其他字符串，它们和已经找到的合法串处于同一删除层，也必须处理。所以我在is_valid(cur)为真时先收集答案、再continue，只有对非法的cur才用if found跳过扩展。这样才能保证把所有同层合法结果都收集全。
4.2 两种解法的取舍：复杂度不是唯一指标
BFS 的时间复杂度理论上也是 O(2^N * N)，空间复杂度 O(2^N * N)，看起来和 DFS 差不多，但它有个明显的短板：如果原串需要删除的括号数很大，BFS 要一层一层删下去，遍历大量中间字符串。比如输入是一长串(((((((((((((((((((((((((，BFS 要删到第 25 层才能得到空串这个合法结果，中间产生的所有中间串都要被生成和判重，非常浪费。
DFS 版本的预扫描会直接告诉它"必须删掉 25 个左括号"，于是一路删到底，几乎没有无效分支。
所以我个人推荐默认用 DFS 版本，它的剪枝信息更充分，代码也更紧凑。BFS 的优势是思考成本低：不需要先理解"配额"这个概念，只要懂层级遍历就能写出来。如果是在面试里，可以先用 BFS 的思路和面试官对齐"按层扩展"的直觉，再手写 DFS 做最终实现。
5. 边界情况与隐藏的坑：实测中容易翻车的地方
这道题代码量不大，但边界情况相当多。我在实际调试和给别人 review 代码时，见过不少次"逻辑看着对，一提交就报错"的案例，下面这几个是最值得注意的。
5.1 常规边界用例速查表
| 输入 | 预期输出 | 说明 |
|---|---|---|
"" | [""] | 空串本身合法 |
"a" | ["a"] | 不含括号，原样返回 |
"(" | [""] | 必须删掉唯一的左括号 |
")(" | [""] | 两个括号都不匹配 |
"()" | ["()"] | 本来就合法，不能多删 |
"(((((((((((((((((((((((((" | [""] | 全左括号，只能全删 |
"(a)())()" | ["(a())()", "(a)()()"] | 普通字母混在中间也要正确处理 |
全左括号这种用例最容易测出问题。如果递归里没有balance == 0的最终校验，或者扫描配额算错，就会把"("、"(("这些中间态也当成答案输出。
5.2 连续重复括号导致的重复答案
前面说过 visited 去重的作用。这里再具体演示一个容易踩的坑：s = "((a"。它的合法结果只有"(a"一个，但如果不做任何去重，DFS 会从"删第 1 个左括号"和"删第 2 个左括号"两条路各走过一次，结果ans里出现两个"(a"。题目要求返回不重复的结果集合，所以这个去重是必须的。
如果你想验证自己的实现有没有踩这个坑，我建议直接用包含连续同种括号的用例去测，比如"((((a))))"。这个输入会产生非常多的重复路径，是去重逻辑的照妖镜。
5.3 递归深度与队列性能
Python 递归深度默认是 1000，而题目字符串长度上限只有 25，递归深度完全不用担心。但要注意，如果在本地测试时把字符串长度改到几百上千，DFS 版本就可能触发递归深度限制，那就要考虑改成显式栈了。
BFS 版本里我用了collections.deque而不是list.pop(0)。list.pop(0)的时间复杂度是 O(N)，每次弹出都要把后面所有元素前移，在字符串数量多的时候会拖慢整体速度。deque.popleft()是 O(1)，刷题时这种实现细节能省一部分运行时间。
6. 从这道题延伸出的通用套路
刷题不能只背答案。这道题表面上是个回溯题，但它背后的方法论可以复用到很多别的题目上。
6.1 "先定配额，再枚举方案"的解题模板
这个套路分三步：
- 用一次贪心扫描确定"必须操作的上限"，比如这里是最少删除的左右括号数；
- 把"删除问题"改写成"逐字符的取舍问题"，递归或者循环里既考虑删也考虑不删；
- 用状态去重 + 合法性剪枝把无效分支提前砍掉。
这套模板不只是括号题能用。比如字符串转有效 IP 地址、复原各种被分隔符切碎的原始串，本质上都是"先确定必须填充/删除的量，再枚举所有组合"。遇到这类题目，先想想能不能把无限枚举压缩成有限决策。
6.2 相关变式题的对比
| 题目方向 | 核心思路 | 和本题的关联 |
|---|---|---|
| 括号生成 | 回溯生成所有合法括号对 | 平衡balance的规则完全一样 |
| 最长有效括号 | 栈或动态规划 | 记的是括号之间的匹配关系 |
| 最少添加使括号有效 | 贪心扫描 | 本题的预扫描就是它的答案 |
| 判断括号是否有效 | 计数器或栈 | 本题的合法性校验函数 |
我自己的体会是，如果能把"删除无效的括号"的预扫描逻辑吃透，那"最少添加"那类题基本就是白送。因为预扫描得到的lrem + rrem恰恰就是最少需要添加的括号数量，连代码都不用怎么改。
最后说一点个人经验。我最初做这道题的时候，第一版写的是纯暴力枚举所有子序列，结果跑到"(((((((((())))))))))"这种用例直接卡死。后来才意识到，回溯题的复杂度瓶颈往往不在"枚举本身"，而在于"怎么证明自己枚举得足够少"。预扫描算配额这一步，就是把指数级问题缩减到"只枚举最少数量的删除方案"的关键。如果你在面试中遇到类似的字符串回溯题，不妨先别急着写递归，花三十秒把那个贪心扫描写好，后面的代码会顺畅很多。这道题刷完之后，建议自己动手把 DFS 和 BFS 两个版本各写三遍，直到能闭眼还原；等写熟了，你会发现很多括号相关的变体题都不再是难题了。
