Backtracking - N-Queens II

The N-Queens puzzle is placing n queens on an n×n chessboard so no two queens attack each other. Return the number of distinct solutions.

Input: n = 4 → Output: 2

Input: n = 1 → Output: 1

Same backtracking as N-Queens but only count solutions instead of building board strings. Track occupied columns and diagonals using three boolean arrays.

Use three boolean arrays: cols[], diag1[] (row-col+n), diag2[] (row+col).
At each row, try placing a queen in each column if not under attack.
Mark the column and diagonals, recurse to next row, then unmark.
Increment counter when all n rows are filled.

class Solution { int count = 0; public int totalNQueens(int n) { backtrack(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]); return count; } private void backtrack(int n, int row, boolean[] cols, boolean[] diag1, boolean[] diag2) { if (row == n) { count++; return; } for (int col = 0; col < n; col++) { int d1 = row - col + n, d2 = row + col; if (cols[col] || diag1[d1] || diag2[d2]) continue; cols[col] = diag1[d1] = diag2[d2] = true; backtrack(n, row + 1, cols, diag1, diag2); cols[col] = diag1[d1] = diag2[d2] = false; } } }

Time Complexity: O(N!) with pruning
Space Complexity: O(N) — boolean arrays + stack