题目描述
给你一个由若干括号和字母组成的字符串 s，请删除最少数量的无效括号，使得输入字符串有效。
返回所有可能的结果。答案可以按任意顺序返回。
这里的“有效括号”指的是：
-
左括号
(必须能够和后面的右括号)配对 -
任意前缀中，右括号数量都不能多于左括号数量
-
最终左括号和右括号数量必须相等
示例分析
示例 1
输入: s = "()())()"
输出: ["(())()","()()()"]
解释：
原字符串中多了一个无效的右括号 )。 删除不同位置的右括号，可以得到两个不同的合法结果：
"(())()"
"()()()"
示例 2
输入: s = "(a)())()"
输出: ["(a())()","(a)()()"]
注意这里不仅有括号，还有普通字符 a。 普通字符不能乱删，它们应该原样保留。
示例 3
输入: s = ")("
输出: [""]
因为这两个括号都无法构成合法匹配，所以只能全部删掉，结果是空字符串。
解题思路
这道题是 LeetCode 里非常经典的一道回溯 / DFS题。
题目的要求其实有两个层面：
-
最终字符串必须是合法括号串
-
删除的括号数量必须最少
也就是说，我们不是只要找到“合法结果”就行，而是要找到：
删除最少括号之后，所有可能得到的最长合法字符串。
你给出的这份代码，核心思想非常巧妙：
-
不是直接去算“删了哪些括号”
-
而是通过 DFS 枚举“当前字符保留还是不保留”
-
最后只保留长度最大的合法结果
因为：
删除最少 等价于 保留最多。
这就是这份代码的关键切入点。
代码
class Solution {
Set<String> set = new HashSet<>();
int n, max, len;
String s;
public List<String> removeInvalidParentheses(String _s) {
s = _s;
n = s.length();
int l = 0, r = 0;
for (char c : s.toCharArray()) {
if (c == '(') l++;
else if (c == ')') r++;
}
max = Math.min(l, r);
dfs(0, "", 0);
return new ArrayList<>(set);
}
void dfs(int u, String cur, int score) {
if (score < 0 || score > max) return ;
if (u == n) {
if (score == 0 && cur.length() >= len) {
if (cur.length() > len) set.clear();
len = cur.length();
set.add(cur);
}
return ;
}
char c = s.charAt(u);
if (c == '(') {
dfs(u + 1, cur + String.valueOf(c), score + 1);
dfs(u + 1, cur, score);
} else if (c == ')') {
dfs(u + 1, cur + String.valueOf(c), score - 1);
dfs(u + 1, cur, score);
} else {
dfs(u + 1, cur + String.valueOf(c), score);
}
}
}
这份代码到底在做什么
这份代码的本质可以概括成一句话：
从左到右扫描字符串，每遇到一个括号，就尝试“保留”或者“删除”；每遇到普通字符，就只能保留。
然后在所有可能的结果中：
-
只保留合法的
-
并且只保留长度最大的那些
也就是说，这份 DFS 枚举的是：
最终字符串的所有保留方案。
为什么“删除最少”可以转化成“保留最多”
题目要求删除最少数量的括号。
假设原字符串长度固定为 n，那么：
-
删除越少
-
保留下来的字符就越多
-
最终结果字符串长度就越大
所以：
删除最少 和 结果长度最大 是等价的。
这就是为什么代码里没有显式记录“删了几个括号”，而是用变量 len 去维护：
当前找到的合法字符串的最大长度
只要最后只保留长度最大的合法结果，就自然满足“删除最少”。
score 表示什么
这份代码里最核心的状态变量就是：
score
它表示：
当前构造出来的字符串
cur中，还没有被匹配掉的左括号数量。
换句话说：
-
遇到
(并保留，score + 1 -
遇到
)并保留，score - 1 -
遇到括号但删除，
score不变 -
遇到普通字符，
score也不变
为什么这个量重要？
因为一个合法括号串必须满足：
-
任何时刻
score都不能小于 0 否则说明右括号比左括号多了，前缀已经非法 -
最终
score必须等于 0 否则说明还有多余的左括号没匹配掉
这两个条件正好可以帮助我们在 DFS 中判断合法性。
为什么 max = Math.min(l, r)
在主函数里，先统计了：
int l = 0, r = 0;
for (char c : s.toCharArray()) {
if (c == '(') l++;
else if (c == ')') r++;
}
max = Math.min(l, r);
这里的 max 表示：
最终合法字符串中，最多能保留多少对括号。
因为一个合法括号串里，左括号数必须等于右括号数。 如果原串中有：
-
l个左括号 -
r个右括号
那么最终最多只能匹配出：
min(l, r)
对括号。
也就是说，未匹配左括号数量 score 不可能超过这个值。 所以在 DFS 中如果发现：
score > max
就可以直接剪枝返回。
DFS 参数分别表示什么
void dfs(int u, String cur, int score)
这三个参数含义很关键：
-
u：当前处理到原字符串的第几个字符 -
cur：当前已经构造出来的字符串 -
score：当前cur中尚未匹配的左括号数量
你可以把这个 DFS 理解为：
从
s[u]开始继续做选择，看看最后能不能构造出一个尽可能长的合法字符串。
代码解析
1. 剪枝：score 不能非法
if (score < 0 || score > max) return ;
这句非常关键。
score < 0
表示当前前缀中右括号太多了。 这种情况一定不可能再变合法，所以直接剪枝。
例如：
")("
如果你一开始保留了 )，那 score = -1，这条路就已经废了。
score > max
表示当前未匹配的左括号数已经太多了。 因为最终最多也只能匹配 max 对括号，再多就没有意义了。
这也是一个有效的剪枝条件。
2. 递归终点：处理完所有字符
if (u == n) {
if (score == 0 && cur.length() >= len) {
if (cur.length() > len) set.clear();
len = cur.length();
set.add(cur);
}
return ;
}
当 u == n 时，说明原字符串已经全部处理完了。
这时只关心两件事：
1）当前字符串是否合法
score == 0
说明所有左括号都成功匹配了，整个字符串合法。
2）当前字符串是不是目前最长的合法结果
cur.length() >= len
如果当前字符串长度比已有结果更大，说明删得更少，是更优解。
3. 如果找到更长的合法结果，要清空旧答案
if (cur.length() > len) set.clear();
因为题目要求的是“删除最少”的结果。
既然当前找到了更长的合法字符串，那么之前那些更短的结果就都不是最优解了，应该全部丢掉。
4. 更新最大长度并加入结果集
len = cur.length();
set.add(cur);
这里用 HashSet 存答案，有两个作用：
-
保存所有最优结果
-
自动去重，避免重复字符串加入
因为在 DFS 过程中，可能通过不同删除路径得到相同结果，所以必须去重。
遇到不同字符时怎么处理
情况 1：当前字符是 (
if (c == '(') {
dfs(u + 1, cur + String.valueOf(c), score + 1);
dfs(u + 1, cur, score);
}
这里有两种选择：
-
保留这个
(-
当前字符串加上它
-
score + 1
-
-
删除这个
(-
当前字符串不变
-
score不变
-
情况 2：当前字符是 )
else if (c == ')') {
dfs(u + 1, cur + String.valueOf(c), score - 1);
dfs(u + 1, cur, score);
}
同样两种选择：
-
保留这个
)-
当前字符串加上它
-
score - 1
-
-
删除这个
)-
当前字符串不变
-
score不变
-
情况 3：当前字符是普通字母
else {
dfs(u + 1, cur + String.valueOf(c), score);
}
普通字符不能删除。 因为题目要求删除的是“无效括号”，字母应该原样保留。
所以这里只有一种选择：直接拼到 cur 后面。
手动模拟一下
以字符串：
s = "()())()"
为例。
我们从左到右做 DFS：
-
遇到
(：可以保留，也可以删 -
遇到
)：可以保留，也可以删 -
不断构造各种
cur
在搜索过程中：
-
若某次保留
)导致score < 0，立即剪枝 -
最后只有
score == 0的结果才算合法 -
在所有合法结果中，只保留长度最大的
最终会得到：
"(())()"
"()()()"
因为它们长度相同，且都是最优解。
为什么 set 可以去重
假设字符串中有多个相同括号，删除不同位置后可能得到同一个结果。
例如某些情况下：
-
删第一个右括号
-
删第二个右括号
最终生成的字符串可能一样。
所以：
Set<String> set = new HashSet<>();
非常必要。
否则答案中可能出现重复项。
这份写法的本质不是“最少删除”，而是“最长合法保留”
这是理解这份代码的最关键一点。
很多题解会直接算：
-
至少要删多少个左括号
-
至少要删多少个右括号
然后 DFS 时按删除数量去控制。
而你这份代码采用的是另一种思路：
不直接算删多少，而是通过最长合法字符串长度来间接保证删除最少。
这个思路非常巧妙，而且代码写起来也很统一。
复杂度分析
这道题本质上是 DFS 枚举，每个括号字符都有“保留 / 删除”两种选择。
如果括号很多，最坏情况下搜索空间接近：
O(2^n)
所以：
时间复杂度
O(2^n)
这是回溯类题常见的指数级复杂度。
空间复杂度
主要来自：
-
递归调用栈
-
当前构造字符串
-
结果集
set
递归栈最坏为：
O(n)
如果把结果集也算上，总空间还要更大。
这道题为什么难
这道题难点不在于语法，而在于思维。
它同时涉及几个关键点：
-
合法括号串判断
-
前缀不能非法
-
最终必须匹配完
-
-
删除最少
-
转化成保留最多
-
-
答案不重复
-
用
HashSet去重
-
-
回溯枚举
-
每个括号都可以“选 / 不选”
-
所以这题不是简单的“写个 DFS”，而是一个非常典型的：
回溯 + 合法性剪枝 + 最优性筛选 + 去重
综合题。
总结
DFS 枚举每个括号保留还是删除，用
score保证括号合法，用len保留最长合法结果，从而实现“删除最少”。
具体来说：
-
每个括号都有“保留 / 删除”两种选择
-
普通字符必须保留
-
score记录未匹配左括号数量 -
score < 0说明前缀非法，立即剪枝 -
最终只保留
score == 0的合法串 -
用
len维护最长合法串长度 -
用
set保证答案不重复
你可以把这题记成一句话：
删除无效括号，本质是“枚举所有保留方案，在合法结果里挑最长的”。
这是一道非常经典、也非常值得反复理解的回溯题。 真正吃透之后，你对“回溯中的状态设计、剪枝和最优解筛选”都会更有感觉。
