class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(res,list,nums,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> list,int[] nums,int start){
        if(start > nums.length) return;
        else{
            res.add(new ArrayList(list));
        }
        for(int i = start;i < nums.length;i++){
            list.add(nums[i]);
            dfs(res,list,nums,i+1);
            list.remove(list.size()-1);
        } 
    }
}

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean visited[][] = new boolean[board.length][board[0].length];
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                if(dfs(board,word,0,visited,i,j)){
                    return true;
                }
            }
        }
        return false;
    }
    // idx 为需要找的word的下标
    // visited 为是否访问过
    // i,j为当前访问元素的行与列下标
    public boolean dfs(char[][] board,String word,int idx,boolean[][] visited,int i,int j){
        if(idx == word.length()-1 && board[i][j] == word.charAt(idx)) return true;
        if(i > board.length || j > board[0].length || i < 0 || j < 0) return false;
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        if(board[i][j] != word.charAt(idx)) return false;
        for(int[] dir:dirs){
            visited[i][j] = true;
            int newi = i + dir[0];
            int newj = j + dir[1];
            if(newi >=0 && newi < visited.length && newj >= 0 && newj < visited[0].length){
                if(!visited[newi][newj]){
                    if(dfs(board,word,idx+1,visited,newi,newj)){
                        return true;
                    }
                }
            } 
            visited[i][j] = false;
        }
        return false;
    }
}

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int leftRemove = 0;
        int rightRemove = 0;
        // 找到左右括号删除最小的数量
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == '('){
                leftRemove++;
            }
            if(s.charAt(i) == ')'){
                if(leftRemove == 0){
                    rightRemove++;
                }else{
                    leftRemove--;
                }
            }
        }
        List<String> res = new ArrayList<>();
        dfs(res,s,leftRemove,rightRemove,0);
        return res;
    }
    public void dfs(List<String> res,String str,int leftRemove,int rightRemove,int idx){
        if(leftRemove == 0 && rightRemove == 0){
            if(isYouXiaoKuoHao(str)){
                res.add(str);
            }
            return;
        }
        for(int i = idx;i < str.length();i++){
            if(i > 0 && str.charAt(i) == str.charAt(i-1)) continue;
            //删除左括号
            if(leftRemove > 0 && str.charAt(i) == '('){
                dfs(res,str.substring(0,i)+str.substring(i+1),leftRemove-1,rightRemove,i);
            }
            //删除右括号
            if(rightRemove > 0 && str.charAt(i) == ')'){
                dfs(res,str.substring(0,i)+str.substring(i+1),leftRemove,rightRemove-1,i);
            }
        }
    }
    public boolean isYouXiaoKuoHao(String s){
        int left = 0,right = 0;
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == '('){
                left++;
            }
            if(s.charAt(i) == ')'){
                right++;
                if(right > left) return false;
            }
        }
        if(left != right) return false;
        return true;
    }
}