🙃301 remove invalid parentheses

https://leetcode.com/problems/remove-invalid-parentheses/submissions/

有点大杂烩的一道题，核心思想的就是每个都试一下保留还是不保留，如果要剪枝就是下面这样

先遍历string统计左右各有几个不匹配的括弧，然后remove直到不匹配的变为0，注意期间仍然要保证左边总数没有右边总数少，同时只有不保留时会减少不匹配数，保留时不会减少不匹配数量

class Solution {
    Set<String> ans = new HashSet<>();
    public List<String> removeInvalidParentheses(String s) {
        char[] array = s.toCharArray();
        int leftUnmatch = 0;
        int rightUnmatch = 0;
        // notice how we get left and right unmatch cnt
        for (int i = 0; i < array.length; i++) {
            char ch = array[i];
            if (ch == '(') leftUnmatch++;
            if (ch == ')') {
                if (leftUnmatch == 0) {
                    rightUnmatch++;
                } 
                if (leftUnmatch > 0) {
                    //we have matched a pair of parentheses
                    leftUnmatch--;
                }
            }
        }
        dfs(array, 0, 0, 0, leftUnmatch, rightUnmatch, new StringBuilder());
        return new ArrayList<>(ans);
    }
    private void dfs(char[] array, int index, int left, int right, int leftUnmatch, int rightUnmatch, StringBuilder sb) {
        if (index == array.length) {
            if (leftUnmatch == 0 && rightUnmatch == 0) ans.add(sb.toString());
            return;
        }
        char ch = array[index];
        // if we discard this ch, we can only discard under certain condition
        // 这里把两个情况合在一起写还是挺优雅的
        if ((ch == '(' && leftUnmatch > 0) || (ch == ')' && rightUnmatch > 0)) {
            dfs(array, index + 1, 
                left, right, 
                leftUnmatch - (ch == '(' ? 1 : 0),
                rightUnmatch - (ch == ')' ? 1 : 0),
                sb
               );
        }
        // if we keep it, there are the following cases
        sb.append(ch);
        if (ch != '(' && ch != ')') {
            dfs(array, index + 1, left, right, leftUnmatch, rightUnmatch, sb);
        } else if (ch == '(') {
            dfs(array, index + 1, left + 1, right, leftUnmatch, rightUnmatch, sb);
        } else {
            if (left > right) {
                // when it's ')', we have to make sure there aren't too many right bracket
                dfs(array, index + 1, left, right + 1, leftUnmatch, rightUnmatch, sb);
            }
        }
        sb.deleteCharAt(sb.length() - 1);
    }
    
}