52. N-Queens II

Follow up for N-Queens problem.

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

Solution:

This problem is a simplified version of N-Queens.

We use the same DFS to keep inserting queens to valid positions.

The only difference is that we do not need to draw the board.



Code:

public class Solution {
    public int sum;
    public int totalNQueens(int n) {
        sum = 0;
        if (n <= 0) {
            return sum;
        }
        int[] col = new int[n];
        helper(n, col, 0);
        return sum;
    }
    public void helper(int n, int[] col, int row) {
        if (row == n) {
            sum++;
            return;
        }
        for (int i = 0; i < n; i++) {
            col[row] = i;
            if (isValid(col, row)) {
                helper(n, col, row + 1);
            }
        }
    }
    public boolean isValid(int[] col, int row) {
        for (int i = 0; i < row; i++) {
            if (col[row] == col[i] || Math.abs(col[row] - col[i]) == row - i) {
                return false;
            }
        }
        return true;
    }
}