// Remove Invalid Parentheses class Solution { unordered_set res; void f(const string &s, string ss, int k, int left, int right, int state) { if (k == s.size()) { if (! left && ! right && ! state) res.insert(ss); return; } if (s[k] == '(') { if (left > 0) f(s, ss, k+1, left-1, right, state); f(s, ss+'(', k+1, left, right, state+1); } else if (s[k] == ')') { if (right > 0) f(s, ss, k+1, left, right-1, state); if (state > 0) f(s, ss+')', k+1, left, right, state-1); } else f(s, ss+s[k], k+1, left, right, state); } public: vector removeInvalidParentheses(string s) { int l = 0, r = 0; for (auto c: s) if (c == '(') l++; else if (c == ')') l ? l-- : r++; f(s, "", 0, l, r, 0); return vector(res.begin(), res.end()); } }; /// O(|ans|). no superfluous enumeration #define REP(i, n) for (int i = 0; i < (n); i++) #define ROF(i, a, b) for (int i = (b); --i >= (a); ) class Solution { vector halves, res; vector milestones, milestones2; int split; // enumerate valid left part: s[0 , split) // invariant: for close parentheses in s[0 , milestones[i]], at least `i+1` of them must be removed void forward(const string &s, string ss, int k, int i, int removed, bool can) { if (k == split) { halves.push_back(ss); return; } if (s[k] == ')') { int ii = k == milestones[i] ? i+1 : i; if (can && removed < milestones.size()) // prefixes of continuous close parentheses can be removed, other parts are disallowed forward(s, ss, k+1, ii, removed+1, true); if (k < milestones[i] || removed > i) // if k == milestones[i], comply with the invariant forward(s, ss+s[k], k+1, ii, removed, false); } else forward(s, ss+s[k], k+1, i, removed, true); } // enumerate valid right part: s[split, n) // for open parentheses in s[milestones2[i] , n), at least `i+1` of them must be removed void backward(const string &s, string ss, int k, int i, int removed, bool can) { if (k == split) { reverse(ss.begin(), ss.end()); for (auto &x: halves) res.push_back(x+ss); return; } k--; if (s[k] == '(') { int ii = i < milestones2.size() && k == milestones2[i] ? i+1 : i; if (can && removed < milestones2.size()) // suffixes of continuous open parentheses can be removed, other parts are disallowed backward(s, ss, k, ii, removed+1, true); if (i == milestones2.size() || k > milestones2[i] || removed > i) // if k == milestones2[i], comply with the invariant backward(s, ss+s[k], k, ii, removed, false); } else backward(s, ss+s[k], k, i, removed, true); } public: vector removeInvalidParentheses(string s) { int unmatched = 0; REP(i, s.size()) if (s[i] == '(') unmatched++; else if (s[i] == ')') { if (unmatched > 0) unmatched--; else milestones.push_back(i); } split = milestones.empty() ? 0 : milestones.back()+1; unmatched = 0; ROF(i, split, s.size()) if (s[i] == ')') unmatched++; else if (s[i] == '(') { if (unmatched > 0) unmatched--; else milestones2.push_back(i); } forward(s, "", 0, 0, 0, true); backward(s, "", s.size(), 0, 0, true); return res; } };