23.02.27 学习

难是真的难，很长很麻烦
两个规则：
1. 满足合法括号的条件；
2. 对于连续重复括号，不考虑删除哪几个括号，枚举删除几个数量的括号

class Solution {
public:
// 合法括号满足的条件：
// 1. 左右括号数量相同；2. 任一前缀中，lr >= rc
// 搜索剪枝
    vector<string> res;

    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (s[i] == '(') l ++ ;
            if (s[i] == ')') {
                if (l == 0) r ++ ;
                else l -- ;
            }
        }
        dfs(s, 0, "", 0, l, r);

        return res;
    }

    void dfs(string& s, int u, string ans, int cnt, int l, int r) {
        if (u == s.size()) {
            if (!cnt) {
                res.push_back(ans);
            }
            return ;
        }

        if (s[u] != '(' && s[u] != ')') dfs(s, u + 1, ans + 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, ans, cnt, l, r);  // 递归搜索
                ans += '(';  // 上面删了，下面的答案需要加上
                cnt ++ , l ++ ;
            }
        } 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 (r >= 0 && cnt >= 0) dfs(s, k, ans, cnt, l, r);
                ans += ')';
                cnt -- , r ++ ;
            }
        }
    }
};