Accepted 4ms c++ solution use backtracking and bitmask, easy understand.








@qkhhly
The time complexity of the improved solution which is the one with line indicators, is


34 lines, 6ms. A little improvement based on your idea.
Using an int array to record the column of queens in previous rows.class Solution {
public:vector<vector<string>> solveNQueens(int n) { vector<vector<string> > res; vector<string> temp(n, string(n,'.')); int dp[n]; helper(res, temp, dp, 0, n); return res; }
private:
void helper(vector<vector<string> > &res, vector<string> &temp, int dp[], int row, int n){ if(row==n){ res.push_back(temp); return; } for(int col=0;col<n;++col){ if(valid(dp, row, col, n)){ dp[row]=col; temp[row][col]='Q'; helper(res, temp, dp, row+1,n); temp[row][col]='.'; } } } bool valid(int dp[], int row, int col, int n){ for(int i=0;i<row;++i){ if(dp[i]==col  abs(rowi)==abs(dp[i]col)){ return false; } } return true; }
};

@ericxu10101 said in Accepted 4ms c++ solution use backtracking and bitmask, easy understand.:
abs(rowi) == abs(dp[i]col) is very smart.