Java concise backtracking solution


  • 1
    W
    public int numberOfPatterns(int m, int n) {
            boolean[][] array = new boolean[3][3];
            int res = 0;
            for(int i = 0;i<3;i++){
                for(int j = 0;j<3;j++){
                    array[i][j]=true;
                    res = res + numberOfPatterns(m,n,1,i,j,array);
                    array[i][j]=false;
                }
            }
            return res;
        }
        
        private int numberOfPatterns(int m,int n,int num,int x,int y,boolean[][] array){
            if(num>n){return 0;}
            int res = num>=m && num<=n? 1: 0;
            for(int i = 0;i<3;i++){
                for(int j = 0;j<3;j++){
                    int a = i-x;
                    int b = j-y;
                    if(array[i][j]||i==x&&j==y || (i==x||j==y||a==b||a==-b) && (Math.abs(a)==2||Math.abs(b)==2)&&!array[(i+x)/2][(j+y)/2]){
                        continue;
                    }else{
                        array[i][j]=true;
                        res = res + numberOfPatterns(m,n,num+1,i,j,array);
                        array[i][j]=false;
                    }
                }
            }
            return res;
        }

  • 0
    L

    Hi @wuzixigua ,
    Thank you for this solution. I had a similar idea but I was not able to figure out the if condition completely. Can you explain why this works? Thanks :)
    if(array[i][j]||i==x&&j==y || (i==x||j==y||a==b||a==-b) && (Math.abs(a)==2||Math.abs(b)==2)&&!array[(i+x)/2][(j+y)/2]){
    continue;
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.