190504

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res =new ArrayList<>();
        List<Integer> t= new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        helpBFS(res,t,nums,visited);
        return res;
        
    }
    public void helpBFS(List<List<Integer>> res,List<Integer> t,int[] nums,boolean[] visited){
        if(t.size()==nums.length){
            List<Integer> temp=new ArrayList<>();
            for(Integer i:t)
                temp.add(i);
            res.add(temp);
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(visited[i]) continue;
            else{
                t.add(nums[i]);
                visited[i]=!visited[i];
                helpBFS(res,t,nums,visited);
                t.remove((Integer)nums[i]);
                visited[i]=!visited[i];
            }
        }
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> t=new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        help(res,t,visited,nums,0);
        return res;
    }
    public void help(List<List<Integer>> res,List<Integer> t,boolean[] visited,int[] nums,int start){
        res.add(new ArrayList(t));
        for(int i=start;i<nums.length;i++){
            if(visited[i]) continue;
            else{
                t.add(nums[i]);
                visited[i]=true;
                help(res,t,visited,nums,i+1); //关键点，从i+1往回再考虑
                visited[i]=false;
                t.remove((Integer)nums[i]);
            }
        }
    }
}

class Solution {
    public boolean exist(char[][] board, String word) {
        if(word.length()>board.length*board[0].length) return false;
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0))
                {
                    boolean[][] visited=new boolean[board.length][board[0].length];
                    visited[i][j]=true;
                    boolean temp=help(i,j,board,word,0,visited);
                    if(temp) return true;
                }
            }
        return false;
    }
    public boolean help(int i,int j,char[][] board,String word,int num,boolean[][] visited){
        if(i<0||i>board.length||j<0||j>board[0].length||word.charAt(num)!=board[i][j]) return false;
        if(num+1==word.length()) return true;
        boolean t1,t2,t3,t4;
        t1=t2=t3=t4=false;
        if(i-1>=0&& board[i-1][j]==word.charAt(num+1)&&visited[i-1][j]==false) {
            visited[i-1][j]=true;
            if(t1=help(i-1,j,board,word,num+1,visited)) return true; 
            visited[i-1][j]=false;
        } 
        if(j+1<board[0].length&&board[i][j+1]==word.charAt(num+1)&&visited[i][j+1]==false) {
            visited[i][j+1]=true;
            if(t2=help(i,j+1,board,word,num+1,visited)) return true;
            visited[i][j+1]=false;  
        } 
        if(i+1<board.length&&board[i+1][j]==word.charAt(num+1)&&visited[i+1][j]==false)  {
            visited[i+1][j]=true;
            if(t3=help(i+1,j,board,word,num+1,visited)) return true;
            visited[i+1][j]=false;
        }
        if(j-1>=0&& board[i][j-1]==word.charAt(num+1)&&visited[i][j-1]==false){
            visited[i][j-1]=true;
            if(t4=help(i,j-1,board,word,num+1,visited)) return true;
            visited[i][j-1]=false;
        } 
        return false;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int i=-1,j=nums.length;
        int k=0;
        while(k<j){
            if(nums[k]==0){
                i++;   
                nums[k]=nums[i];
                nums[i]=0;                 
                k++;
            }
            else if(nums[k]==2){
                j--;    
                nums[k]=nums[j];
                nums[j]=2;                
            }
            else k++;
        }
    }
}