1
class Solution {
2
 public:
3
  void back_tracking(vector<string> &res, string cus, int lp, int rp, int idx) {
4
    if (!lp && !rp) {
5
      int invalid = 0;
6
      bool flag = true;
7
      for (int i = 0; i < cus.size(); i++) {
8
        if (cus[i] == '(')
9
          invalid++;
10
        else if (cus[i] == ')') {
11
          invalid--;
12
          if (invalid < 0) {
13
            flag = false;
14
            break;
15
          }
16
        }
17
      }
18
      if (flag) res.emplace_back(cus);
19
      return;
20
    }
21

22
    for (int i = idx; i < cus.size(); i++) {
23
      if (i != idx && cus[i] == cus[i - 1]) continue;
24

25
      if (lp + rp > cus.size() - i) return;
26

27
      if (lp && cus[i] == '(')
28
        back_tracking(res, cus.substr(0, i) + cus.substr(i + 1), lp - 1, rp, i);
29

30
      if (rp && cus[i] == ')')
31
        back_tracking(res, cus.substr(0, i) + cus.substr(i + 1), lp, rp - 1, i);
32
    }
33
  }
34

35
  vector<string> removeInvalidParentheses(string s) {
36
    int left_p = 0;
37
    int right_p = 0;
38
    for (auto &ch : s) {
39
      if (ch == '(')
40
        left_p++;
41
      else if (ch == ')') {
42
        if (left_p > 0)
43
          left_p--;
44
        else
45
          right_p++;
46
      }
47
    }
48
    vector<string> res;
49
    back_tracking(res, s, left_p, right_p, 0);
50
    return res;
51
  }
52
};