Java: fast and space saving code use DFS and bit manipulation


  • 0
    F
    private int res = 0;
    public int totalNQueens(int n) {
        if (n <= 0) return res;
        helper(n, 0, 0, 0, 0);
        return res;
    }
    
    private void helper(int n, int ind, int col, int left, int right) {
        if (ind == n) {
            res++;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if ((col >> i & 1) == 0 && (left >> i - ind + n - 1 & 1) == 0 && (right >> ind + i & 1) == 0) {
                col |= 1 << i;
                left |= 1 << i - ind + n -1;
                right |= 1 << ind + i;
                
                helper(n, ind + 1, col, left, right);
                
                col &= ~(1 << i);
                left &= ~(1 << i - ind + n -1);
                right &= ~(1 << ind + i);
            }
        }
    }

Log in to reply
 

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