链接：https://leetcode-cn.com/problems/remove-invalid-parentheses/

题目

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

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

用例

示例 1：

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

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

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

思路

方法一
dfs回溯
遍历记录需要删除的左括号和右括号的数量
如果为左括号 left++
如果为右括号 当left>0时 left--
left<0时 说明右括号不匹配 right++
然后回溯删除括号

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int left=0,right=0;
        for(auto ss:s){
            if(ss=='('){
                left++;
            }else if(ss==')'){
                if(left>0){
                    left--;
                }else{
                    right++;
                }
            }
        }
        string son;
        backtracking(s,0,left,right,son);
        return vector<string>(ans.begin(),ans.end());

    }
private:
    stack<int>st;
    unordered_set<string>ans;
    void backtracking(string &s,int index,int left,int right,string &sonans){
        if(index==s.size()){
            if(left==0&&right==0){
                for(auto ss:sonans){
                    if(ss=='(')left++;
                    else if(ss==')'){
                        if(left>0)left--;
                        else right++;
                    }
                }
                if(left==0&&right==0)
                    ans.insert(sonans);
            }
            return;
        }
        if(s[index]=='('&&left>0){
            left--;
            backtracking(s,index+1,left,right,sonans);
            left++;
        }else if(s[index]==')'&&right>0){
            right--;
            backtracking(s,index+1,left,right,sonans);
            right++;
        }
        sonans+=s[index];
        backtracking(s,index+1,left,right,sonans);
        sonans.pop_back();
    }
};

实际上可以继续剪枝
当回溯过程钟每次都检查当前序列括号是否匹配

class Solution {
public:
    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int lremove = 0;
        int rremove = 0;

        for (char c : s) {
            if (c == '(') {
                lremove++;
            } else if (c == ')') {
                if (lremove == 0) {
                    rremove++;
                } else {
                    lremove--;
                }
            }
        }
        helper(s, 0, 0, 0, lremove, rremove);
        return res;
    }

    void helper(string str, int start, int lcount, int rcount, int lremove, int rremove) {
        if (lremove == 0 && rremove == 0) {
            if (isValid(str)) {
                res.push_back(str);
            }
            return;
        }

        for (int i = start; i < str.size(); i++) {
            if (i != start && str[i] == str[i - 1]) {
                continue;
            }
            // 如果剩余的字符无法满足去掉的数量要求，直接返回
            if (lremove + rremove > str.size() - i) {
                return;
            } 
            // 尝试去掉一个左括号
            if (lremove > 0 && str[i] == '(') {
                helper(str.substr(0, i) + str.substr(i + 1), i, lcount, rcount, lremove - 1, rremove);
            }
            // 尝试去掉一个右括号
            if (rremove > 0 && str[i] == ')') {
                helper(str.substr(0, i) + str.substr(i + 1), i, lcount, rcount, lremove, rremove - 1);
            }
            if (str[i] == ')') {
                lcount++;
            } else if (str[i] == ')') {
                rcount++;
            }
            // 当前右括号的数量大于左括号的数量则为非法,直接返回.
            if (rcount > lcount) {
                break;
            }
        }
    }

    inline bool isValid(const string & str) {
        int cnt = 0;

        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '(') {
                cnt++;
            } else if (str[i] == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }

        return cnt == 0;
    }
};

方法二
bfs
要求最少删除
可以每一轮删除一个括号，知道出现合法字符串为止 出现的这轮即为最小删除次数，用hash表去重

class Solution {
public:
    bool isValid(string str){
        int count=0;
        for(auto s:str){
            if(s=='(')count++;
            else if(s==')'){
                count--;
                if(count<0)
                    return false;
            }
        }
        return count==0;
    }
    vector<string> removeInvalidParentheses(string s) {
        vector<string>ans;
        unordered_set<string>currSet;
        currSet.insert(s);
        while(true){
            for(auto &str:currSet){
                if(isValid(str))
                    ans.push_back(str);
            }
            if(ans.size()>0){
                return ans;
            }
            unordered_set<string>nextSet;
            for(auto &str:currSet){
                for(int i=0;i<str.size();i++){
                    if(i>0&&str[i]==str[i-1])
                        continue;
                    if(str[i]=='('||str[i]==')'){
                        nextSet.insert(str.substr(0,i)+str.substr(i+1,str.size()));
                    }
                }
            }
            currSet=nextSet;
        }
    }  
};