###### tags: `LeetCode` `Recursion` `Hard`
# LeetCode #301 [Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)
### (Hard)

給你一個由若干括號和字母組成的字符串 s ，刪除最小數量的無效括號，使得輸入的字符串有效。

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

---

首先要計算出多餘的左括號與右括號, 多餘的右括號發生在右括號數量大於左括號時, 而多餘的左括號數量則是最後結算時多於右括號的數量。

得知多餘的左右括號數量後, 即可得到需要消除多少個括號才能達成有效字串, 此時的暴力法就是使用DFS不斷消除括號直到消除數量等於多餘括號, 此時檢查剩下的字串是否為有效字串, 若是則將該字串加入答案數組中。

這個方法雖然正確但或許不是最好的, 因為是窮舉所有組合再去篩選是否為有效字串, 不確定是否有方法能夠消除正確的多餘括號(不需要額外判斷為合法字串的方法)。

---

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int left=0, right=0;
        vector<string> ans;
        for(auto c:s){
            if(c=='(')left++;
            else if(c==')'){
                if(left)left--;
                else if(!left)right++;
            }
        }
        dfs(s, 0, left+right, ans);
        return ans;
    }
    void dfs(string& s, int pos, int count, vector<string>& ans){
        if(isvalid(s)&&count==0){
            ans.push_back(s);
            return;
        }
        for(int i=pos;i<s.length();i++){
            if(i!=pos&&s[i]==s[i-1])continue;
            if(s[i]=='('||s[i]==')'){
                if(count>0){
                    string curr=s;
                    curr.erase(i,1);
                    dfs(curr, i, count-1, ans);
                }
            }
        }
    }
    bool isvalid(string s){
        int n=0;
        for(auto c:s){
            if(c=='(')n++;
            else if(c==')')n--;
            if(n<0)return false;
        }
        return n==0;
    }
};