301. Remove Invalid Parentheses

样例

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

(DFS) $O(2^N)$

一开始计算rmL和rmR表示应该删掉rmL个’(‘ 和 rmR个’)’。然后DFS，对于每一个char，我都可以选或者不选，选的话，就要append，不选的话需要把相应的rmL/rnR减1。还需要一个open来记录当前的stringbuilder是不是valid的。

JAVA 代码

    public List<String> removeInvalidParentheses(String s) {
        int rmL = 0, rmR = 0;
        for (char c:s.toCharArray()) {
            if (c == '(') {
                rmL++;
            } else if (c == ')') {
                if (rmL > 0) {
                    rmL--;
                } else {
                    rmR++;
                }
            }
        }
        Set<String> set = new HashSet<>();
        dfsHelp (s.toCharArray(), 0, new StringBuilder(), set, rmL, rmR, 0);
        List<String>res = new ArrayList<>();
        res.addAll(set);
        return res;
    }
    private void dfsHelp (char[] c, int index, StringBuilder sb, Set<String> set, int rmL, int rmR, int open) {
        if (rmL < 0 || rmR < 0 || open < 0) {
            return;
        }
        if (index == c.length) {
            if (rmL == 0 && rmR == 0 && open == 0) {
                set.add(sb.toString());
            }
            return;
        }
        int len = sb.length();
        if (c[index] == '(') {
            dfsHelp(c, index + 1, new StringBuilder(sb), set, rmL - 1, rmR, open);               // no use this c
            dfsHelp(c, index + 1, new StringBuilder(sb).append('('), set, rmL, rmR, open + 1);     // use this c
        } else if (c[index] == ')') {
            dfsHelp(c, index + 1, new StringBuilder(sb), set, rmL, rmR - 1, open);                // no use this c
            dfsHelp(c, index + 1, new StringBuilder(sb).append(')'), set, rmL, rmR, open - 1);     // use this c
        } else {
            dfsHelp(c, index + 1, sb.append(c[index]), set, rmL, rmR, open);
        }

    }