题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

思路

DFS 回溯算法：

首先最终合法的方案，必然有左括号的数量 = 右括号的数量

如果左括号的得分为 1；右括号的得分为 -1，那么对于合法的方案而言，必定满足最终得分为 0

同时可以预处理出「爆搜」过程的最大得分： max = min(左括号的数量, 右括号的数量)，其中「爆搜」过程的最大得分必然是：合法左括号先全部出现在左边，之后使用最多的合法右括号进行匹配。

枚举过程中出现字符分三种情况：

• 普通字符：无须删除，直接添加
• 左括号：如果当前得分不超过 max - 1 时，可以选择添加该左括号，也能选择不添加
• 右括号：如果当前得分大于 0（说明有一个左括号可以与之匹配），可以选择添加该右括号，也能选择不添加

使用 Set 进行方案去重，len 记录「爆搜」过程中的最大子串，然后将所有结果集中长度为 len 的子串加入答案。

java代码如下：

class Solution {Set set = new HashSet<>();int n, max, len;String s;public List 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很容易漏掉max = Math.min(l, r);dfs(0, "", 0);return new ArrayList<>(set);}// u: 字符串下标，表示当前要处理原始字符串u下标的字符。u其实也是递归的深度// cur: 增加)、(、普通字符后的字符串// score: 增加)、(、普通字符后的得分void dfs(int u, String cur, int score) {// 不得不佩服 score > max 这个判断if (score < 0 || score > max) return ;// n: 原始字符串长度// u == n 代表对原始字符串处理完成了if (u == n) {// score == 0 代表 cur 字符串合法if (score == 0 && cur.length() >= len) {// 这里为什么要对set进行clear？// len 代表啥？叶姐原话：len 记录「爆搜」过程中的最大子串，然后只保留长度等于 lenlen 的子串。// 什么情况下 cur.length() > len?// 先追溯 len 的赋值。len是由上一次入列时的cur.length赋值的，现在的cur.length > len，说明cur变长了// 以 "(a)()" 字符串为例，执行到此的cur，可能为 "a"或"(a)", set里放的，可能就是"a"，而"a"不是我们要的答案,所以clear// clear 会不会把合法的字符串给清掉。自然不会，有上面的len限制着，短字符串没这个能力进来clearif (cur.length() > len) set.clear();len = cur.length();// 入列set.add(cur);}return ;}// 注意：u是对源字符串进行取数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);}}
}