LeetCode 301. 删除无效的括号-526互联

class Solution {
public:
    vector<string> ans;
    vector<string> removeInvalidParentheses(string s) {
        //lr分别记录要删除的左右括号数量
        int l=0,r=0;
        for(auto c:s)
            if(c=='(')  l++;
            else if(c==')')
            {
                if(l==0)    r++;
                else l--;
            }
        dfs(s,"",0,l,r);
        return ans;
    }
    bool check(string s)
    {
        int cnt = 0,n = s.length();
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] =='(') cnt ++;
            else if(s[i] == ')') cnt --;
            if(cnt < 0) return false;
        }
        return cnt == 0;
    }
    void dfs(string s,string path,int u,int l,int r)//枚举删除哪些括号
    {
        int n=s.size();
        if(u>=n)
        {
            if(check(path))
                ans.push_back(path);
            return;
        }
        if(s[u]=='(')
        {
            //找出连续括号数量
            int t=u;
            while(t<n&&s[t]=='(')   t++;
            //倒序枚举删除的数量
            l-=t-u;
            for(int i=t-u;i>=0;i--)
            {
                if(l>=0)
                    dfs(s,path,t,l,r);
                path=path+'(';
                l++;
            }
        }
        else if(s[u]==')')
        {
            //找出连续括号数量
            int t=u;
            while(t<n&&s[t]==')')   t++;
            //倒序枚举删除的数量
            r-=t-u;
            for(int i=t-u;i>=0;i--)
            {
                if(r>=0)
                    dfs(s,path,t,l,r);
                path=path+')';
                r++;
            }
        }
        else//当前不是括号，直接递归下一步    
            dfs(s,path+s[u],u+1,l,r);
    }
};