## N-Queens II

• Time:O(n \cdot n!)
• Space:O(n \cdot n!)

## C++

class Solution {
public:
int totalNQueens(int n) {
int ans = 0;
dfs(n, 0, vector<bool>(n), vector<bool>(2 * n - 1), vector<bool>(2 * n - 1),
ans);
return ans;
}

private:
void dfs(int n, int i, vector<bool>&& cols, vector<bool>&& diag1,
vector<bool>&& diag2, 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, move(cols), move(diag1), move(diag2), ans);
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
}
}
};


## JAVA

class Solution {
public int totalNQueens(int n) {
dfs(n, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
return ans;
}

private int ans = 0;

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

for (int j = 0; j < cols.length; ++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);
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
}
}
}


## Python

class Solution:
def totalNQueens(self, n: int) -> int:
ans = 0
cols = [False] * n
diag1 = [False] * (2 * n - 1)
diag2 = [False] * (2 * n - 1)

def dfs(i: int) -> None:
nonlocal ans
if i == n:
ans += 1
return

for j in range(n):
if cols[j] or diag1[i + j] or diag2[j - i + n - 1]:
continue
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = True
dfs(i + 1)
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = False

dfs(0)
return ans