52. N-Queens II Leetcode Java

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Solution:

Instead of output the all possible solution, this problem only need the number of possible solution.

Almost the same with N-Queens

The difference is in the base case: Instead of output the solution, we just need to increment the number of solution.

if(row>n) {res[0]++};

Tips:

In java, Integer is immutable, in order to update the number through the recursion, we have to wrap it with an array or arraylist or anything else, I use an array here, so each time, I increment res[0] which will reflect the number of possible solutions.

  public int totalNQueens(int n) {  
   if (n==0) return 0;  
   int[] res= new int[1];  
   int[] column=new int[n];  
   helper(res,1,n,column);  
   return res[0];  
   }  
   public void helper(int[] res, int row, int n, int[] column){  
     if(row>n) {  
       res[0]=res[0]+1;  
       return;  
     }  
     for(int i=0;i<n;i++){  
       column[row-1]=i;  
       if(isValid(column,row-1,i)) helper(res,row+1,n,column);  
     }  
   }  
   public boolean isValid(int[] column,int i, int j){  
     for(int k=0;k<i;k++){  
       if(column[k]==j || i-k==Math.abs(j-column[k])) return false;  
     }  
     return true;  
   }