**BFS: ** remove i parenthesis and add to queue, when one is valid then no need to remove more, but poll out all the possible string out to see if they are valid, add to result if they are valid.

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<String>();
        Set<String> visited = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        queue.offer(s);
        visited.add(s);
        boolean found = false;
        while(!queue.isEmpty()){
            String cur = queue.poll();
            if(isValid(cur)){
                res.add(cur);
                found = true;
            }
            if(found) continue;//KEY: to keep removal minimum. a valid found, no need to next level
            for(int i = 0; i < cur.length(); i++){
                if(cur.charAt(i) != '(' && cur.charAt(i) != ')') continue; 
                String sub = cur.substring(0, i) + cur.substring(i+1, cur.length());
                if(!visited.contains(sub)){
                    queue.offer(sub);
                    visited.add(sub);
                }
            }
        }
        return res;
    }
    private boolean isValid(String s){
        int count  = 0;
        char[] sc = s.toCharArray();
        for(int i = 0; i < sc.length; i++){
            if(sc[i] == '(') count++;
            if(sc[i] == ')'){
                if(count == 0) return false;
                count--;
            }
        }
        return count == 0;
    }
}