# My C++ DFS+Backtracking solution (O(N) memory, O(N^2) time )

• The same idea as N-QUEEN, use three bool arraies to track if the current column (indexed by col), diagonal line (indexed by row-col+N), or the anti-diagonal line (indexed by row+col) is available (i.e., no other queen is already put on that line); do DFS and backtracking from row 1 to row N-1 for each column.

``````class Solution {
private:
void  dfs(int &res, int row, int N, bool colValid[], bool diagValid[], bool antiDiagValid[])
{
if(row==N) ++res;
else{
for(auto col=0; col<N; ++col)
{
if(colValid[col] && diagValid[row-col+N] && antiDiagValid[row+col])
{
colValid[col] = diagValid[row-col+N] = antiDiagValid[row+col] = false;
dfs(res, row+1, N, colValid, diagValid, antiDiagValid);
colValid[col] = diagValid[row-col+N] = antiDiagValid[row+col] = true;
}
}
}
}

public:
int totalNQueens(int n) {
if(n<=0) return 0;

int res =0;
bool colValid[n], diagValid[2*n], antiDiagValid[2*n];
fill_n(colValid, n, true);
fill_n(diagValid,2*n, true);
fill_n(antiDiagValid, 2*n, true);

dfs(res, 0, n, colValid, diagValid, antiDiagValid);
return res;
}
};``````

• By using dfs, why O(N^2) time??

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.