301. 删除无效的括号(dfs)

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

class Solution {
public:
    set<string> res;
    void dfs(string path,int level,string& s,int l_cnt, int r_cnt,int min_cnt) {
        if (l_cnt < r_cnt || l_cnt> min_cnt || r_cnt>min_cnt || level>s.size()) return;
        if (level == s.size()) {
            if (l_cnt==r_cnt && l_cnt == min_cnt) {
                res.insert(path);
            }
        }
        char c = s[level];
        if (c =='(') {
            dfs(path+c,level+1,s,l_cnt+1,r_cnt,min_cnt);
            dfs(path,level+1,s,l_cnt,r_cnt,min_cnt);
        } else if (c == ')') {
            dfs(path+c,level+1,s,l_cnt,r_cnt+1,min_cnt);
            dfs(path,level+1,s,l_cnt,r_cnt,min_cnt);
        } else {
            dfs(path+c,level+1,s,l_cnt,r_cnt,min_cnt);
        }
    }
    vector<string> removeInvalidParentheses(string s) {
        int l_cnt = 0;
        int r_cnt = 0;
        for(auto c: s) {
            if (c=='(') l_cnt++;
            else if (c==')') { // )( 避免这种case
                if (l_cnt > r_cnt) {
                r_cnt++;
                }
            }
        }
        int min_cnt = min(l_cnt,r_cnt);
        dfs("",0,s,0,0,min_cnt);
        vector<string> out;
        for(auto i : res) {
            out.emplace_back(i);
        }
        return out;
    }
};