### leetcode Question 60: N-Queens II

N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:

Same idea just a little bit difference from the previous one.

Note:
If I use the vector as the data structure, the code cannot pass the large online judge, however, if I use the dynamic array, which successfully pass all the online judge test. What the hell? lol

Source Code:

class Solution {
public:
int res;

bool isValid(int A[], int r){
for (int i=0;i<r;i++){
if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){
return false;
}
}
return true;
}
void nqueens(int A[], int cur, int n){
if (cur==n){ res++;return;}
else{
for (int i=0;i<n;i++){
A[cur]=i;
if (isValid(A,cur)){
nqueens(A,cur+1,n);
}
}
}
}
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
res=0;
int *A = new int[n];
nqueens(A,0,n);
return res;
}
};


#### 4 comments:

1. Hi Yu, why it does not work if I use vector A(n, -1) instead of A[n]? Anything else is the same as yours but I can not still get AC on leetcode.

1. Hi there, I'm also not sure why this situation happens, one reason might be that the memory of holding a vector is larger than the dynamic array?

2. Hi Yu, I do not think that is the reason because in the previous Queens1 problem we can use vector. Why can't we do it this time? Maybe we should ask 1337. :)

2. Hi Yu, the reason is you'd better use reference vector &A instead of vector A to avoid necessary vector copy. Then you just modify your code a little bit. Then good.