N-Queens II(Hard)

Leetcode Source

Follow up for N-Queens problem.

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

集合法

复杂度

时间 O(N^2) 空间 O(N) 思路

跟I的解法一样，只不过把原本构造字符串的地方换成了计数器加一。

public class Solution {

    Set<Integer> rowSet = new HashSet<Integer>();
    Set<Integer> diag1Set = new HashSet<Integer>();
    Set<Integer> diag2Set = new HashSet<Integer>();
    int cnt = 0;

    public int totalNQueens(int n) {
        helper(n, 0);
        return cnt;
    }

    public void helper(int n, int col){
        if(col == n){
            cnt++;
        } else {
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
            }
        }
    }
}