题目

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

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

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

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

解题思路

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

递归函数

设计递归函数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);
        }
    }