Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

方法1: backtracking/dfs

花花酱：https://www.youtube.com/watch?v=2k_rS_u6EBk

思路：

1. 遍历第一遍统计有多少个非法的“(”，以及非法的“)”，赋值为 l 和 r，也就是交给dfs需要删除的括号数量。
2. 开始dfs。在dfs的过程中，退出条件是l = 0 && r == 0，此时可以合法推入一个结果。如果还没有删完，需要遍历字串，尝试删除一个"(“或”)"（看哪个还需要）。这个过程中可以用到技巧剪枝：1. 如果当前的i不是"(“或”)"，可以跳过， 2， 对于有多种删除选择但是导致的结果相同时，我们选择跳过。这种情况仅发生在类似“())”或"((" 这种情况，也就是出现多个重复的左右括号。那么为了减掉这些可以通过 if (i != start && s[i] == s[i - 1]) continue。start是每次dfs传递进来的string需要开始尝试删除的位置。为什么记录这个呢？因为这个值之前的字符如果需要我们都已经尝试过删除了，再从头开始会产生很多重复计算。而且利用这个数字也可以来去重。删除的操作是s.erase(i, 1)去掉这个字符。注意这时的start就会移交给 i，因为之前的我们也在本循环内都递归删除过了。

易错点

1. 统计合法的时候（两次都包括）不要粗暴的else if，因为还可能有其他字符，要检查确实是“(”或者")"。
2. 这里的dfs不要用&，或者像下面的方法一样用&但是单独拷贝出一个current，因为要定点再恢复current不太容易。
3. start的传递：移交给 i。

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (char c: s){
            if (c == '('){
                l++;
            }
            else if (l <= 0 && c == ')'){
                r++;
            }
            else if (c == ')'){
                l--;
            }
        }
        vector<string> result;
        dfs(s, 0, result, l, r);
        return result;
    }
    
    void dfs(string  s, int start, vector<string> & result, int l, int r){
        if (l == 0 && r == 0){
            if (isValid(s)){
                result.push_back(s);
                return;
            }
            
        }
        
        for (int i = start; i < s.size(); i++){
            if (i != start && s[i] == s[i - 1]) continue;
            if (s[i] == '(' || s[i] == ')'){
                string current = s;
                current.erase(i, 1);
                if (r > 0 && s[i] == ')'){
                    dfs(current, i, result, l, r - 1);
                }
                if (l > 0 && s[i] == '('){
                    dfs(current, i, result, l - 1, r);
                }
            }
        }
        return;
    }
    
    bool isValid(string & t){
        int count = 0;
        for (char c: t){
            if (c == '('){
                count++;
            }
            if (c == ')'){
                count--;
            }
            if (count < 0) return false;
        }
        return count == 0;
    }
};
// l = 0, r = 1
// "(   a   )   (   )   )   (   )"
//          i
// start = 0

方法2: bfs

grandyang: http://www.cnblogs.com/grandyang/p/4944875.html