52. N-Queens II

Time: O(n!)

Space: O(n)

Intuition

Same as N-Queens I but count solutions instead of collecting them. The backtracking logic is identical; replace board recording with a counter increment.

Algorithm

1Same backtracking as N-Queens I, but when row == n: count++.
2Return count.

Example Walkthrough

Input: n = 4

1.Same search as problem 51 finds 2 complete placements.

Output: 2

Common Pitfalls

•Bit manipulation alternative: use integer bitmasks for cols/posDiag/negDiag to speed up the inner loop.

52.cs

// Approach: DFS with three boolean arrays for column, major diagonal, and minor
// diagonal to count all valid queen placements.
// Time: O(n!) Space: O(n)

public class Solution
{
    public int TotalNQueens(int n)
    {
        int ans = 0;
        Dfs(n, 0, new bool[n], new bool[2 * n - 1], new bool[2 * n - 1], ref ans);
        return ans;
    }

    private void Dfs(int n, int i, bool[] cols, bool[] diag1, bool[] diag2, ref int ans)
    {
        if (i == n)
        {
            ans++;
            return;
        }

        for (int j = 0; j < n; j++)
        {
            if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
                continue;
            cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
            Dfs(n, i + 1, cols, diag1, diag2, ref ans);
            cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
        }
    }
}

Was this solution helpful?