52. N Queens II - cocoder39/coco39_LC GitHub Wiki

52. N-Queens II

class Solution {
public:
    int totalNQueens(int n) {
        int res = 0;
        int full1 = (1 << n) - 1;
        helper(res, 0, full1, 0, 0, 0);
        return res;
    }
private:
    void helper(int& res, int row, int full1, int maskCol, int mask45, int mask135) {
        if (maskCol == full1) {
            res++;
            return;
        }
        
        int position = full1 & (~(maskCol | mask45 | mask135));
        while (position) {
            int pos = position & (~position + 1);
            position -= pos;
            int col = 0;
            int p = pos;
            while (p & 1) {
                p >>= 1;
                col++;
            }
            helper(res, row + 1, full1, maskCol | pos, (mask45 | pos) << 1, (mask135 | pos) >> 1);
        }
    }
};