Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

class Solution { public: vector<string> removeInvalidParentheses(string s) { vector<string> sol; if (s.size() == 0) { return {""}; } // Extra paren. int left_paren = 0, right_paren = 0; for (auto ch : s) { if (ch == '(') { left_paren++; } else if (ch == ')') { if (left_paren > 0) { left_paren--; } else { right_paren++; } } } set<string> sol_set; dfs(s, 0, left_paren, right_paren, "", sol_set); sol = vector<string>(sol_set.begin(), sol_set.end()); return sol; } void dfs(string s, int idx, int left_paren, int right_paren, string ans, set<string>& sol) { if (idx == s.size()) { if (left_paren == 0 && right_paren == 0) { if (valid(ans)) { sol.insert(ans); } } return; } for (int i = idx; i < s.size(); i++) { if (s[i] == '(' && left_paren > 0) { left_paren--; dfs(s, i + 1, left_paren, right_paren, ans, sol); left_paren++; } if (s[i] == ')' && right_paren > 0) { right_paren--; dfs(s, i + 1, left_paren, right_paren, ans, sol); right_paren++; } ans += s[i]; } if (left_paren == 0 && right_paren == 0) { if (valid(ans)) { sol.insert(ans); } } } bool valid(string s) { int left = 0; for (auto ch : s) { if (ch == '(') { left++; } else if (ch == ')') { if (left <= 0) { return false; } left--; } } return true; } };

========= Cleaner one ======

public:

  vector<string> removeInvalidParentheses(const string& s) {        

    int l = 0;

    int r = 0;

 

    for (const char ch : s) {

      l += (ch == '(');

      if (l == 0)

        r += (ch == ')');

      else

        l -= (ch == ')');

    }

 

    vector<string> ans;

    dfs(s, 0, l, r, ans);

    return ans;

  }

private:

  bool isValid(const string& s) {

    int count = 0;

    for (const char ch : s) {

      if (ch == '(') ++count;

      if (ch == ')') --count;

      if (count < 0) return false;

    }

    return count == 0;

  }

 

  // l/r: number of left/right parentheses to remove.

  void dfs(const string& s, int start, int l, int r, vector<string>& ans) {

    // Nothing to remove.

    if (l == 0 && r == 0) {

      if (isValid(s)) ans.push_back(s);

      return;

    }

 

    for (int i = start; i < s.length(); ++i) {

      // We only remove the first parenthes if there are consecutive ones to avoid duplications.

      if (i != start && s[i] == s[i - 1]) continue;

 

      if (s[i] == '(' || s[i] == ')') {

        string curr = s;

        curr.erase(i, 1);

        if (r > 0 && s[i] == ')')

          dfs(curr, i, l, r - 1, ans);

        else if (l > 0 && s[i] == '(')

          dfs(curr, i, l - 1, r, ans);

      }

    }

  }