Description

Submission

class Solution {
    vector<string> rets;
    int maxLen;
    void dfs(string& s, string cur, int left, int step) {
        if(left < 0) return;
        if(cur.size() > maxLen) return;
        if(step == s.length()) {
            if(left == 0 && cur.length() == maxLen) {
                rets.push_back(cur);
            }
            return;
        }

        if(s[step] != '(' && s[step] != ')') {
            dfs(s, cur + s.substr(step, 1), left, step+1);
        } else {
            dfs(s, cur + s.substr(step, 1), left + (s[step] == '(' ? 1 : -1), step + 1);
            if(cur.empty() || cur.back() != s[step]) {
                dfs(s, cur, left, step + 1);
            }
        }
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        int len = s.length();
        int left = 0, remove = 0;

        for(char ch: s) {
            if(ch == '(') ++left;
            else if(ch == ')') {
                if(left) --left;
                else ++remove;
            }
        }

        maxLen = len - left - remove;
        string cur;
        dfs(s, cur, 0, 0);

        return rets;
    }
};