1
class Solution {
2
  public List<String> removeInvalidParentheses(String s) {
3
    List<String> ans = new ArrayList<>();
4
    HashSet<String> set = new HashSet<String>();
5

6
    int minBracket = removeBracket(s);
7
    getAns(s, minBracket, set, ans);
8

9
    return ans;
10
  }
11

12
  public void getAns(String s, int minBracket, HashSet<String> set, List<String> ans) {
13
    if (set.contains(s)) return;
14

15
    set.add(s);
16

17
    if (minBracket == 0) {
18
      int remove = removeBracket(s);
19
      if (remove == 0) ans.add(s);
20
      return;
21
    }
22

23
    for (int i = 0; i < s.length(); i++) {
24
      if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
25
      String L = s.substring(0, i);
26
      String R = s.substring(i + 1);
27

28
      if (!set.contains(L + R)) getAns(L + R, minBracket - 1, set, ans);
29
    }
30
  }
31

32
  public int removeBracket(String s) {
33
    Stack<Character> stack = new Stack<>();
34

35
    for (int i = 0; i < s.length(); i++) {
36
      char x = s.charAt(i);
37

38
      if (x == '(') stack.push(x);
39
      else if (x == ')') {
40
        if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
41
        else stack.push(x);
42
      }
43
    }
44
    return stack.size();
45
  }
46
}