# 52. N-Queens II

## 1.問題&#x20;

* 對n \* n大小的棋盤, 回傳有多少種n queen的排法?

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNESCIiGEMvlfaEHyNH%2F-LNEQXsyz21nVq0qEPPU%2F2018092502.jpg?alt=media\&token=b7340eb1-9d34-44b1-a058-a03fd6d6c687)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  col, row, diagonal都只能有一個queen
* parameter
  * n
  * new row
  * col list
  * cnt
* test input
* 說明想法
  * 與51. N-Queens的概念相同, 只是在newRow == n (最後一個row)時讓cnt + 1
  * DFS
    * base case: 當new row == n時return
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int totalNQueens(int n) {
        vector<int> col;
        int cnt = 0;
        solveNQ(n, col, 0, cnt);
        return cnt;
    }
private:
    void solveNQ(int n, vector<int>& col, int newRow, int & cnt) {
        if (newRow == n) {
            ++cnt;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(col, i, newRow)) {
                col.push_back(i);
                solveNQ(n, col, newRow + 1, cnt);
                col.pop_back();
            }
        }
    }
    bool isValid(vector<int>& col, int newCol, int newRow){
        for (int i = 0; i < col.size(); i++) {
            if (newCol == col[i] ||
                abs(newCol - col[i]) == abs(newRow - i)) {
                return false;
            }
        }
        return true;
    }
};
```
