This problem can be solved very elegantly using BFS, as in .

The code is rewritten below in C++.

1 class Solution { 2 public: 3     vector
     
       removeInvalidParentheses(string s) { 4         vector
      
        parens; 5         queue
       
         candidates; 6         unordered_set
        
          visited; 7         candidates.push(s); 8         visited.insert(s); 9         bool found = false;10         while (!candidates.empty()) {11             string now = candidates.front();12             candidates.pop();13             if (isValid(now)) {14                 parens.push_back(now);15                 found = true;16             }17             if (!found) {18                 int n = now.length();19                 for (int i = 0; i < n; i++) {20                     if (now[i] == '(' || now[i] == ')') {21                         string next = now.substr(0, i) + now.substr(i + 1);22                         if (visited.find(next) == visited.end()) {23                             candidates.push(next);24                             visited.insert(next);25                         }26                     }27                 }28             }29         }30         return parens;31     }32 private:33     bool isValid(string& s) {34         int c = 0, n = s.length();35         for (int i = 0; i < n; i++) {36             if (s[i] == '(') c++;37             if (s[i] == ')' && !c--) return false;38         }39         return !c;40     }41 };