---

题目

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

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

示例 1：

输入：s = “()())()”
输出：[“(())()”,“()()()”]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-invalid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

首先
怎么判断一一个括号字符串是有效的

假设我不考虑左括号多的情况，我只考虑右括号多的情况，那么我从头到尾遍历整个字符串
有两个东西:
i:检查的位置,
j:可能删除的位置
一开始i, j都在0位置
count:
一个变量，遇到左括号++,右括号–
如果count没有到0以下，说明每一个右括号都能找到与之配对的左括号
当右括号多的时候，就要删除了

到12位置的时候, count<0,
开始检查,2位置为第一个右扩号,删除2位置的右括号
当你做了一个在2位置删除掉右括号的决定之后，你在3位置，如果发现你左侧也是右括号，不要做在3位置删除的决定
决定删除哪个右括号是由右括号左边决定的
如果是右括号,则不用删除
如果是左括号,则删除

接下来5位置做删除决定
接下来9位置可以做出删除的决定，但10跟11位置要跳过

递归函数

设计递归函数f(i,j)
i检查位置,j删除位置
f(i,j), 一开始是f(0, 0)
检查位置从0开始查起，删除位置从0开始

如果要删除括号,调用递归f(i,j)
直接return当前递归,后续过程交给后面的递归

当遍历完count记录左括号
在遍历count记录右扩号
最后得出答案

代码

	public static List<String> removeInvalidParentheses(String s) {
		List<String> ans = new ArrayList<>();
		remove(s, ans, 0, 0, new char[] { '(', ')' });
		return ans;
	}
	public static void remove(String s, List<String> ans, int checkIndex, int deleteIndex, char[] par) {
		for (int count = 0, i = checkIndex; i < s.length(); i++) {
			if (s.charAt(i) == par[0]) {
				count++;
			}
			if (s.charAt(i) == par[1]) {
				count--;
			}
			// i check计数<0的第一个位置
			if (count < 0) {
				for (int j = deleteIndex; j <= i; ++j) {
					// 比如
					if (s.charAt(j) == par[1] && (j == deleteIndex || s.charAt(j - 1) != par[1])) {
						remove(
								s.substring(0, j) + s.substring(j + 1, s.length()),
								ans, i, j, par);
					}
				}
				return;
			}
		}
		String reversed = new StringBuilder(s).reverse().toString();
		if (par[0] == '(') {
			remove(reversed, ans, 0, 0, new char[] { ')', '(' });
		} else {
			ans.add(reversed);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33