LeetCode-N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

据说没有递推公式

class Solution {
public:
    int check(int* X,int k){
        for(int i=0;i<k;i++){
            if(X[i]==X[k]||abs(X[i]-X[k])==abs(i-k))return -1;
        }
        return 0;
    }
    int totalNQueens(int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int ret=0;
        int* X=new int[n+1];
        X[0]=-1;
        int j=0;
        while(j>=0)
        {
            X[j]++;
            if(X[j]==n)
            {
                j--;
                continue;
            }
            if(check(X,j)<0)
            {
                    continue;
            }
            else
            {
                j++;
                if(j==n){
                    ret++;
                    j--;
                }
                else
                {
                    X[j]=-1;
                }
            }
        }
        delete X;
        return ret;
    }
};