参考文献

ref

合法括号序列的判断条件：
1.左右括号数量相同
2.任意一个前缀中，左括号数量 >= 右括号数量

C++ 代码

class Solution {
public:
    // 计算需要删除的左括号数量l，需要删除的右括号数量r
    // 利用上述结论提前剪枝
    // 以及需要避免重复，即 ((( 这几个左括号删除一个结果都一样，因此需要枚举删除的数量

    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for(char c : s){
            if(c == '(')l++;
            if(l==0 && c == ')')r++;
            else if(c == ')')l--;
        }
        // cout << l << "," << r << endl;
        dfs(s, 0, "", 0, l, r);
        return res;
    }

    // s:原字符串，u:当前搜索到的字符串下标，path:当前的结果字符串
    // cnt: 左括号减右括号的值；l:剩余左括号的数量；r：剩余右括号的数量
    void dfs(string s, int u, string path, int cnt, int l, int r){
        if(u == s.size()){
            if(!cnt){
                res.push_back(path);
            }
            return;
        }

        if(s[u]!='(' && s[u]!=')')dfs(s, u+1, path+s[u], cnt, l, r);
        else if(s[u] == '('){
            // 计算连续的(数量，然后枚举删除几个
            int k = u;
            while(k<s.size() && s[k]=='(')k++;
            l -= k-u; // 先假设一次性删除完连续的左括号
            for(int i=k-u; i>=0; i--){
                if(l>=0)dfs(s, k, path, cnt, l, r);
                // 每次再补回来一个 (
                l++, cnt++;
                path += '(';
            }
        } else if(s[u] == ')'){
            int k = u;
            while(k<s.size() && s[k]==')')k++;
            r -= k-u;
            // 每次再补回来一个 )
            for(int i=k-u; i>=0; i--){
                // 需要满足 左括号数量大于右括号，且还可以删除右括号
                if(cnt >=0 && r>=0)dfs(s, k, path, cnt, l, r);
                r++, cnt--;
                path += ')';
            }
        }
    }
};