回溯：N 皇后（约束搜索与剪枝）

一、面试常考点

1. 剪枝思路

列冲突、主对角线冲突、副对角线冲突立即剪枝。

2. 状态表示

用集合记录已占用列和两种对角线。

二、细节介绍

1. 递归层级

按“行”递归，每行放一个皇后。

2. 对角线编码

主对角线 row-col，副对角线 row+col。

三、示例代码（计数版）

function totalNQueens(n) {
  let ans = 0
  const cols = new Set()
  const diag1 = new Set()
  const diag2 = new Set()

  function dfs(row) {
    if (row === n) {
      ans++
      return
    }

    for (let col = 0; col < n; col++) {
      const d1 = row - col
      const d2 = row + col
      if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) continue

      cols.add(col)
      diag1.add(d1)
      diag2.add(d2)
      dfs(row + 1)
      cols.delete(col)
      diag1.delete(d1)
      diag2.delete(d2)
    }
  }

  dfs(0)
  return ans
}

四、常用应用场景

1. 约束满足问题

排班、调度、资源冲突分配。

2. 搜索剪枝题

复杂组合空间中的可行解筛选。