LeetCode-52-N-Queens-II

class Solution {
public:
    int totalNQueens(int n) {
        vector<int> rows(n),d1(2*n-1),d2(2*n-1);
        return find(n,n,0,rows,d1,d2);
    }
    int find(int n,int left,int i,vector<int>& rows,vector<int>& d1,vector<int>& d2){
        if(left==0)
            return 1;
        int j,sum=0;
        for(j=0;j<n;++j){
            if(rows[j]||d1[i+j]||d2[n-1+i-j])
                continue;
            rows[j]=d1[i+j]=d2[n-1+i-j]=1;
            sum+=find(n,left-1,i+1,rows,d1,d2);
            rows[j]=d1[i+j]=d2[n-1+i-j]=0;
        }
        return sum;
    }
};

class Solution {
public:
    int totalNQueens(int n) {
        bool flag[5*n] = {false};
        int num = 0;
        dfs(num,flag,0,n);
        return num;
    }
    void dfs(int& num, bool* flag, int row, int n){
        if(row == n){
            ++num;
            return;
        }
        for(int i = 0; i<n;i++){
            if(!flag[i] && !flag[row+i+n] && !flag[4*n + row - i]){
                flag[i] = 1;
                flag[row+i+n] = 1;
                flag[4*n + row - i] = 1;
                dfs(num,flag,row+1,n);
                flag[i] = 0;
                flag[row+i+n] = 0;
                flag[4*n + row - i] = 0;
            }
        }
    }
};