52. N-Queens II

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        if (n <= 1) {
            return n;
        }

        HashSet<Integer> cols = new HashSet<Integer>();
        HashSet<Integer> diags1 = new HashSet<Integer>();
        HashSet<Integer> diags2 = new HashSet<Integer>();
        totalNQueensUtil(n, 0, cols, diags1, diags2);
        return count;
    }

    public void totalNQueensUtil(int n, int row, HashSet<Integer> cols, HashSet<Integer> diags1, HashSet<Integer> diags2) {
        if (row == n) {
            count++;
        } else {
            for (int i=0; i<n; i++) {
                int diag1 = row - i;
                int diag2 = row + i;

                if (cols.contains(i) || diags1.contains(diag1) || diags2.contains(diag2)) {
                    continue;
                }

                cols.add(i);
                diags1.add(diag1);
                diags2.add(diag2);
                totalNQueensUtil(n, row+1, cols, diags1, diags2);
                cols.remove(i);
                diags1.remove(diag1);
                diags2.remove(diag2);
            }
        }
    }
}