52. N-Queens II

1.問題

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

2.想法

• 提問

  • 確認題意: 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.程式碼

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;
    }
};