52. N 皇后2

题号：52
来源：LeetCode
难度：困难
标签：回溯 递归
语言：TypeScript
解法：1 个
作者：lmliheng
最近更新：2026-09-27

TypeScript · O(n!) 时间 · O(n) 空间 · 更新于 2026-09-27

回溯计数，布尔数组判列与对角线冲突

typescript

/**
 * @difficulty hard
 * @tags 回溯,递归
 * @time O(n!)
 * @space O(n)
 * @note 回溯计数，布尔数组判列与对角线冲突
 * @52. N 皇后 II
 */


var totalNQueens = function (n: number) {
    let res = 0
    //let quene = new Array(n).fill(-1)
    let colUsed = new Array(n).fill(false)
    let diag1 = new Array(2 * n - 1).fill(false)
    let diag2 = new Array(2 * n - 1).fill(false)


    const dfs = (r: number) => {
        if (r > n - 1) {
            res++
            //  console.log([...quene])
            return
        }
        for (let col = 0; col < n; col++) {
            if ((!colUsed[col]) && (!diag1[r + col] && (!diag2[r - col + n - 1]))) {
                //quene[r] = col
                colUsed[col] = diag1[r + col] = diag2[r - col + n - 1] = true
                dfs(r + 1)
                // 回退

                colUsed[col] = diag1[r + col] = diag2[r - col + n - 1] = false

            }
        }
    }

    dfs(0)
    return res
};

源码：ts/leetcode/52. N 皇后2.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm

52. N 皇后2 ​

52. N 皇后2