class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {

        unordered_set<string>st;

        int lcnt = 0, rcnt = 0;

        for(char c:s){

            if(c == '(')lcnt++;
            if(c == ')'){

                if(lcnt > 0)
                {
                    lcnt--;
                }
                else rcnt++;
            }
        }

        dfs(s, 0, lcnt, rcnt, 0, "", st);

        vector<string>ans(st.begin(), st.end());

        return ans;

    }

    void dfs(string s, int id, int lremove, int rremove, int pair, string path, unordered_set<string>&st )
    {
        if(id == s.size())
        {
            if( lremove == 0 && rremove == 0 && pair == 0)
            {
                st.insert(path);
            }
            return;
        }
        if( lremove < 0 || rremove < 0 && pair < 0 ) return;
        char c = s[id];

       if( c != '(' && c != ')')
       {
           dfs(s, id+1, lremove, rremove, pair, path+s[id], st);
           return;
       }

        if( c == ')')
        {
            if( rremove > 0 )
            {
                dfs(s, id+1, lremove, rremove-1, pair, path, st);
            }

            if( pair > 0 )
                dfs(s, id+1, lremove, rremove, pair-1, path+s[id], st);
        }

          if( c == '(')
        {
            if( lremove > 0 )
            {
                dfs(s, id+1, lremove-1, rremove, pair, path, st);
            }
            dfs(s, id+1, lremove, rremove, pair+1, path+s[id], st);
        }


    }
};