301. 删除无效的括号

class Solution {
public:
    bool isValid(string &s){
        int cnt=0;
        for(char c:s){
            if(c=='(')
                cnt++;
            else if(c==')')
                cnt--;
            if(cnt<0)
                return false;
        }
        return cnt==0;
        
    }
    vector<string> res;
    void dfs(string s, int start, int lremove, int rremove){
        if(lremove==0&&rremove==0){
            if(isValid(s))
                res.push_back(s);
            return ;
        }
        for(int i=start;i<s.length();i++){
            if(i>start&&s[i]==s[i-1])
                continue;
            if(lremove+rremove>s.length()-i)
                return ;
            if(lremove>0&&s[i]=='(')
                dfs(s.substr(0,i)+s.substr(i+1), i, lremove-1, rremove);
            if(rremove>0&&s[i]==')')
                dfs(s.substr(0,i)+s.substr(i+1), i, lremove, rremove-1);
        }
        
    }
    vector<string> removeInvalidParentheses(string s) {
        int lremove,rremove;
        lremove=rremove=0;

        for(char c:s){
            if(c=='(')
                lremove++;
            else if(c==')')
                if(lremove==0)
                    rremove++;
                else
                    lremove--;
        }
        
        dfs(s, 0, lremove, rremove);
        return res;

    }
};