Simple yet efficient solution 0ms in C++


  • 0
    class Solution {
    private:
        int search(int n, int r, vector<int>& forward, vector<int>& backward, vector<int>& cols)
        {
            if(n == r) return 1;
            int sum = 0;
            for(int c = 0; c < n; ++c)
            {
                if(!forward[r+c] && !backward[n+r-c-1] && !cols[c])
                {
                    forward[r+c] = backward[n+r-c-1] = cols[c] = 1;
                    sum += search(n, r+1, forward, backward, cols);
                    forward[r+c] = backward[n+r-c-1] = cols[c] = 0;
                }
            }
            return sum;
        }
    
    public:
        //AC - best submission;
        int totalNQueens(int n) 
        {
            vector<int> forward(2*n-1), backward(2*n-1), cols(n); //using int is more efficient than bool;
            return search(n, 0, forward, backward, cols);
        }
    };

Log in to reply
 

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