| 题目链接 | 52. N 皇后 II |
|---|---|
| 思路 | 经典回溯题 |
| 题解链接 | 【视频】回溯秒杀N皇后！一个视频讲透！（Python/Java/C++/Go/JS） |
| 关键点 | 无 |
| 时间复杂度 | \(O(n!)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class Solution:
def totalNQueens(self, n: int) -> int:
m = n * 2 - 1
answer = 0
on_path = [False] * n
diag1 = [False] * m
diag2 = [False] * m
def dfs(r):
if r == n:
nonlocal answer
answer += 1
return
for c, on in enumerate(on_path):
if not on and not diag1[r + c] and not diag2[r - c]:
on_path[c] = diag1[r + c] = diag2[r - c] = True
dfs(r+1)
on_path[c] = diag1[r + c] = diag2[r - c] = False
dfs(0)
return answer