题目链接
思路：dfs+剪枝
核心思想是，对于每个字符，只有两种可能，放入\不放入，枚举即可

首先探索一下答案的长度。然后进行dfs
使用一个变量n来记录字符串的总长度
使用变量len来记录答案的长度
count来记录括号的对数
len和count的区别在于，字符串中可能存在字母，所以len>=2*count
记录这些是为了进行剪枝。

class Solution {HashSet<String> removeInvalidParenthesesSet = new HashSet<>();String s_ = "";int count = 0,n;int len = 0;StringBuilder sb = new StringBuilder();public List<String> removeInvalidParentheses(String s) {s_ = s;n = s.length();int l = 0, r = 0;int l1 = 0, r1=0;for(char c : s.toCharArray()){if(c=='('){l++;l1++;}else if(c==')') {if (l != 0) {l--;} else {r++;}r1++;}}len = n - l - r;count = Math.min(l1,r1);//最多可能存在的括号数目（单边）dfs(0,0);ArrayList<String> list = new ArrayList<>();removeInvalidParenthesesSet.stream().forEach(s1 -> {list.add(s1);});return list;}/**** @param index 当前枚举到的下标* @param countCur 当前的括号数（左边）  左右括号是可以抵消的*/public void dfs(int index,int countCur){//减枝  当前括号数大于了可能的最大数目    小于0了if(countCur>count || countCur<0){return;}//当  遍历完了，此时进行判断是否是答案if(index == n){//当前括号数不多不少  左右相等  并且长度等于正确答案的长度if(countCur==0 && sb.length() == len){removeInvalidParenthesesSet.add(sb.toString());}return;}char c = s_.charAt(index);if(c=='('){//放进去sb.append(c);dfs(index+1,countCur+1);sb.deleteCharAt(sb.length()-1);//不放进去dfs(index+1,countCur);}else if(c == ')'){//放进去sb.append(c);dfs(index+1,countCur-1);sb.deleteCharAt(sb.length()-1);//不放进去dfs(index+1,countCur);}else{sb.append(c);dfs(index+1,countCur);sb.deleteCharAt(sb.length()-1);}}
}