N-Queens II

Follow up for N-Queens problem.

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

Have you met this question in a real interview? 

Yes

Example

For n=4, there are 2 distinct solutions.

class Solution {

    /**

     * Calculate the total number of distinct N-Queen solutions.

     * @param n: The number of queens.

     * @return: The total number of distinct solutions.

     */

    public int totalNQueens(int n) {

        //write your code here

        

        return dfs(n, 0, new int[n]);

    }

    

    

    private int dfs(int n, int start, int[] row){

        int res = 0;

        if(n == start){

            return 1;

        }

        for(int i = 0; i < n; i++){

            row[start] = i;

            boolean isValid = true;

            for(int j = 0; j < start; j++){

                if(row[j] == i || Math.abs(row[j] - row[start]) == start - j){

                    isValid = false;

                    break;

                }

               

            }

            

            if(isValid == true){

                res +=  dfs(n, start+1, row);

            }

        }

        return res;

    }

    

};