52.N皇后Ⅱ

题目描述

题解

回溯算法

这道题做法与上道题一模一样, 甚至更简单些, 只需要求出不同解决方案的数量即可. 免去了数组转为字符串的过程

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        List<Integer> path = new ArrayList<>();
        boolean[] col = new boolean[n];
        boolean[] main = new boolean[n*2-1];
        boolean[] sub = new boolean[n*2-1];
        dfs(n, 0, path, col, main, sub);
        return count;
    }

    private void dfs(int n, int step, List<Integer> path, boolean[] col, boolean[] main, boolean[] sub){
        if(step == n){
            count++;
            return;
        }

        for(int i = 0;i < n;i++){
            if(!col[i]&&!main[step-i+n-1]&&!sub[step+i]){
                path.add(i);
                col[i] = true;
                main[step - i + n - 1] = true;
                sub[step + i] = true;
                dfs(n, step+1, path, col, main, sub);

                path.remove(path.size() - 1);
                col[i] = false;
                main[step - i + n - 1] = false;
                sub[step + i] = false;
            }
        }

    }

}