回溯（题单顺序）

热题 100 - 回溯分组（按题单顺序）：46 / 78 / 17 / 39 / 22 / 79 / 131 / 51

本页包含题单「回溯」分组的全部题目，顺序与 list.json 保持一致。

回溯的核心（点击展开）

把“所有可能”看成一棵决策树，DFS 走下去，走不通就撤销选择（backtrack）换一条路。

46. 全排列

力扣原题：46. 全排列

Medium

数组

回溯

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

最优解（回溯：用 used 标记已选元素）

正在加载编辑器...

Rust 参考（点击展开）

fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut res = vec![];
    let mut path = vec![];
    let mut used = vec![false; n];
    fn dfs(nums: &[i32], path: &mut Vec<i32>, used: &mut Vec<bool>, res: &mut Vec<Vec<i32>>) {
        if path.len() == nums.len() { res.push(path.clone()); return; }
        for i in 0..nums.len() {
            if used[i] { continue; }
            used[i] = true; path.push(nums[i]);
            dfs(nums, path, used, res);
            path.pop(); used[i] = false;
        }
    }
    dfs(&nums, &mut path, &mut used, &mut res);
    res
}

fn main() {
    println!("{}", permute(vec![1,2,3]).len());   // 6
    println!("{:?}", permute(vec![0,1]));          // [[0,1],[1,0]]
    println!("{:?}", permute(vec![1]));            // [[1]]
    println!("{}", permute(vec![1,2,3,4]).len());  // 24
    println!("{}", permute(vec![-1,0,1]).iter().any(|p| *p == vec![-1,0,1])); // true
}

最优解讲解（通俗版 + 推理过程）

题意翻译：把数组里的每个数字都用一次，生成所有不同的排列顺序。
为什么天然是回溯？
你可以把它想成“填空题”：
- 第 1 个位置放谁？
- 第 2 个位置放谁？
- … 每一步都有多个候选，选错了就换别的，这正是决策树 + DFS 的场景。
状态怎么设计（写回溯最关键的一步）：
- path：当前已经选出来的前缀排列（长度就是当前深度）
- used[i]：nums[i] 是否已经被用过（保证“每个元素只用一次”）
递归终止条件为什么是 path.length === nums.length？
因为排列必须用满所有元素，长度达到 n 就是一组完整答案，拷贝 path 记录即可（必须 slice()，否则后面回溯会把它改掉）。
回溯的核心动作永远就两步：
1. 做选择：used[i]=true + path.push(nums[i])
2. 撤销选择：path.pop() + used[i]=false
用一个小例子走一遍：[1,2,3]
- 先选 1 → 再选 2 → 再选 3 → 得到 [1,2,3]
- 回退：把 3 弹出，换成 2 的其它选择（这里没有）→ 再回退到 1 的层
- 让第二个位置换成 3 → 形成 [1,3,2]
- 再回到第一层把 1 换成 2/3……最终得到 6 种
复杂度直觉：分支数是 (n \times (n-1) \times \dots \times 1)，也就是 (O(n!))（输出本身就这么多）。

类似题目（排列/组合回溯模板）

function dfs() {
  if (endCondition) { record(); return }
  for (choice of choices) {
    if (invalid(choice)) continue
    make(choice)
    dfs()
    undo(choice)
  }
}

78. 子集

力扣原题：78. 子集

Medium

位运算

数组

回溯

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

最优解（回溯：每个位置“选/不选”）

正在加载编辑器...

Rust 参考（点击展开）

fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut res = vec![];
    let mut path = vec![];
    fn dfs(nums: &[i32], start: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        res.push(path.clone());
        for i in start..nums.len() {
            path.push(nums[i]);
            dfs(nums, i + 1, path, res);
            path.pop();
        }
    }
    dfs(&nums, 0, &mut path, &mut res);
    res
}

fn main() {
    println!("{}", subsets(vec![1,2,3]).len()); // 8
    println!("{:?}", subsets(vec![0]));          // [[], [0]]
    println!("{:?}", subsets(vec![]));           // [[]]
    println!("{}", subsets(vec![1,2,3,4]).len()); // 16
    println!("{}", subsets(vec![1,2]).len());    // 4
}

最优解讲解（通俗版 + 推理过程）

子集的本质：对每个元素只有两种决定——“选它”或“不选它”，所以总数是 (2^n)。
为什么还用回溯？：位运算枚举当然能做，但回溯是“组合题通用语言”，后面遇到约束/剪枝时更好扩展。
start 的意义（避免重复的关键）：
- 子集不看顺序，所以 [1,2] 和 [2,1] 是同一个。
- 我们规定：下一次只能从 start 往后选，这样路径永远是按下标递增生成的，自然不会出现顺序颠倒导致的重复。
为什么“每到一个节点都要记录一次 path”？
- 在这棵树里，任何一个节点都代表“当前已经选出来的集合”，它本身就是一个合法子集。
- 所以进入 dfs(start) 的那一刻，就应该把 path 放进答案。
小例子：[1,2,3]
- 先记录 []
- 选 1 → 记录 [1] → 再选 2 → [1,2] → 再选 3 → [1,2,3]
- 回退后改选 3 → [1,3]
- 回到根层改选 2 → [2]、[2,3]；改选 3 → [3]
- 一共 8 个，正好 (2^3)。
复杂度：输出规模本身是 (2^n)，所以时间/空间至少也是这个量级。

类似题目（组合类：start 控制下一步可选范围）

dfs(start):
  record(path)
  for i from start..:
    choose i
    dfs(i+1)
    undo

17. 电话号码的字母组合

力扣原题：17. 电话号码的字母组合

Medium

哈希表

字符串

回溯

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = "2"
输出：["a","b","c"]

提示：

1 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

最优解（回溯：每一位数字选一个字母）

正在加载编辑器...

Rust 参考（点击展开）

fn letter_combinations(digits: &str) -> Vec<String> {
    if digits.is_empty() { return vec![]; }
    let map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    let digits: Vec<usize> = digits.bytes().map(|b| (b - b'0') as usize).collect();
    let mut res = vec![];
    let mut path = String::new();
    fn dfs(digits: &[usize], map: &[&str], pos: usize, path: &mut String, res: &mut Vec<String>) {
        if pos == digits.len() { res.push(path.clone()); return; }
        for ch in map[digits[pos]].chars() {
            path.push(ch);
            dfs(digits, map, pos + 1, path, res);
            path.pop();
        }
    }
    dfs(&digits, &map, 0, &mut path, &mut res);
    res
}

fn main() {
    println!("{}", letter_combinations("23").len()); // 9
    println!("{}", letter_combinations("").len());   // 0
    println!("{:?}", letter_combinations("2"));       // ["a","b","c"]
    println!("{}", letter_combinations("79").len()); // 16
    println!("{}", letter_combinations("234").len()); // 27
}

最优解讲解（通俗版 + 推理过程）

把题目看成“固定长度的多叉树”：digits 有几位，就有几层要做选择。
- 第 pos 层要做的事：从 digits[pos] 对应的字母集合里挑 1 个。
为什么回溯很合适？
- digits 长度不固定（可能 1 位、2 位、4 位……），用回溯就不需要写很多层嵌套循环。
- 每一层都做同样的动作：“遍历当前可选字母 → 选择一个 → 进入下一层 → 回退”。
状态是什么？
- pos：当前处理到第几位数字
- path：已经拼好的前缀字符串（用数组存字符，最后 join）
终止条件为什么是 pos === digits.length？
- 说明每一位都已经选了一个字母，路径长度也等于 digits 长度，此时 path.join("") 就是一组完整答案。
小例子：digits="23"
- "2" → a/b/c；"3" → d/e/f
- 所以答案是 3×3=9 个：ad, ae, ..., cf。
复杂度直觉：答案数量本身是各位分支数的乘积（最坏每位 4 个字母，所以最多 (4^n)）。

类似题目（固定长度多叉选择：按位置递归）

dfs(pos):
  if pos==n: record
  else for ch in choices[pos]: choose; dfs(pos+1); undo

39. 组合总和

力扣原题：39. 组合总和

Medium

数组

回溯

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

最优解（回溯：可重复选，同一层 i 不变）

正在加载编辑器...

Rust 参考（点击展开）

fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    candidates.sort();
    let mut res = vec![];
    let mut path = vec![];
    fn dfs(cands: &[i32], start: usize, remain: i32, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        if remain == 0 { res.push(path.clone()); return; }
        for i in start..cands.len() {
            if cands[i] > remain { break; }
            path.push(cands[i]);
            dfs(cands, i, remain - cands[i], path, res);
            path.pop();
        }
    }
    dfs(&candidates, 0, target, &mut path, &mut res);
    res
}

fn main() {
    println!("{:?}", combination_sum(vec![2,3,6,7], 7)); // [[2,2,3],[7]]
    println!("{:?}", combination_sum(vec![2,3,5], 8));    // [[2,2,2,2],[2,3,3],[3,5]]
    println!("{:?}", combination_sum(vec![2], 1));         // []
    println!("{:?}", combination_sum(vec![1], 2));         // [[1,1]]
    println!("{}", !combination_sum(vec![2,3,6,7], 200).is_empty()); // true
}

最优解讲解（通俗版 + 推理过程）

题意翻译：从候选数里选若干个数（允许重复使用同一个候选），凑出 target；输出所有组合（组合不看顺序）。
先分清“组合 vs 排列”：
- 组合不看顺序：[2,2,3] 和 [2,3,2] 应该算同一个答案。
- 所以我们必须在生成过程中避免“同一组数的不同顺序”。
start 的意义：保证组合按非递减顺序构造
- 下一次只能从 start 开始选，等价于“只能选当前数或更大的数”。
- 这样就不会出现先选 3 再选 2 的情况，自然去重。
为什么递归用 dfs(i, remain-x)？
- 因为题目允许重复使用 candidates[i]，所以选了 x 之后，下一层仍然可以继续选 i（不跳到 i+1）。
排序是为了剪枝，不是为了去重：
- 当候选已排序后，如果 x > remain，后面只会更大，直接 break。
- 这能大量减少无意义分支。
终止条件：
- remain == 0：刚好凑满，记录 path
- remain < 0：这条路超了（由于剪枝，代码里不会走到负数）
小例子：candidates=[2,3,6,7], target=7
- 先选 2 → remain=5 → 继续选 2 → remain=3 → 选 3 → remain=0 得到 [2,2,3]
- 直接选 7 → remain=0 得到 [7]
复杂度：本质取决于答案数量与剪枝效果，回溯题通常以“搜索树大小”为主导。

类似题目（可重复选：递归仍从 i 开始）

for i from start..:
  choose a[i]
  dfs(i, remain-a[i]) // repeat allowed
  undo

22. 括号生成

力扣原题：22. 括号生成

Medium

字符串

动态规划

回溯

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

最优解（回溯 + 剪枝：左括号剩余 & 右括号合法性）

正在加载编辑器...

Rust 参考（点击展开）

fn generate_parenthesis(n: usize) -> Vec<String> {
    let mut res = vec![];
    let mut path = String::new();
    fn dfs(n: usize, open: usize, close: usize, path: &mut String, res: &mut Vec<String>) {
        if open == n && close == n { res.push(path.clone()); return; }
        if open < n  { path.push('('); dfs(n, open+1, close, path, res); path.pop(); }
        if close < open { path.push(')'); dfs(n, open, close+1, path, res); path.pop(); }
    }
    dfs(n, 0, 0, &mut path, &mut res);
    res
}

fn main() {
    println!("{:?}", generate_parenthesis(1)); // ["()"]
    println!("{}", generate_parenthesis(3).len()); // 5
    println!("{:?}", generate_parenthesis(2));      // ["(())", "()()"]
    println!("{:?}", generate_parenthesis(0));      // [""]
    println!("{}", generate_parenthesis(4).len()); // 14
}

最优解讲解（通俗版 + 推理过程）

为什么这题必须剪枝？：长度是 2n 的括号串一共有 (2^2) 种，先全生成再过滤会爆炸。
合法括号串的两条铁律（不变量）：
1. 最终：左括号和右括号都恰好用 n 个
2. 过程中任意前缀：右括号数量永远不能超过左括号数量（否则会出现“还没开就先关”的非法状态）
把不变量直接写进递归条件，就是最强剪枝：
- openUsed < n 才能放 '('（否则左括号超量）
- closeUsed < openUsed 才能放 ')'（保证任意前缀合法）
小例子（n=3）帮你理解为什么 closeUsed < openUsed 必须有：
- 如果一上来就放 ')'，不管后面怎么补，都不可能变成合法串，所以这条分支应该立刻剪掉。
终止条件：当 openUsed==n && closeUsed==n，长度正好 2n，且一路都合法，记录答案。
复杂度直觉：仍然是指数级（答案数是卡特兰数），但我们只走“可能合法”的分支，实际数量远小于 (2^2)。

类似题目（生成合法序列：用计数维护前缀合法性）

if openUsed < n: add "("
if closeUsed < openUsed: add ")"

79. 单词搜索

力扣原题：79. 单词搜索

Medium

深度优先搜索

数组

字符串

回溯

矩阵

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

最优解（回溯 DFS：从每个格子出发尝试匹配）

正在加载编辑器...

Rust 参考（点击展开）

fn exist(mut board: Vec<Vec<u8>>, word: &[u8]) -> bool {
    let (m, n) = (board.len(), board[0].len());
    fn dfs(board: &mut Vec<Vec<u8>>, word: &[u8], i: usize, j: usize, k: usize) -> bool {
        if board[i][j] != word[k] { return false; }
        if k == word.len() - 1 { return true; }
        let tmp = board[i][j]; board[i][j] = b'#';
        let dirs: [(i32,i32); 4] = [(1,0),(-1,0),(0,1),(0,-1)];
        let m = board.len() as i32; let n = board[0].len() as i32;
        for (di,dj) in dirs {
            let ni = i as i32+di; let nj = j as i32+dj;
            if ni>=0 && ni<m && nj>=0 && nj<n && board[ni as usize][nj as usize]!=b'#' {
                if dfs(board, word, ni as usize, nj as usize, k+1) { board[i][j]=tmp; return true; }
            }
        }
        board[i][j] = tmp; false
    }
    for i in 0..m { for j in 0..n { if dfs(&mut board, word, i, j, 0) { return true; } } }
    false
}

fn b(s: &[&str]) -> Vec<Vec<u8>> { s.iter().map(|r| r.bytes().collect()).collect() }

fn main() {
    println!("{}", exist(b(&["ABCE","SFCS","ADEE"]), b"ABCCED")); // true
    println!("{}", exist(b(&["ABCE","SFCS","ADEE"]), b"SEE"));    // true
    println!("{}", exist(b(&["ABCE","SFCS","ADEE"]), b"ABCB"));   // false
    println!("{}", exist(b(&["a"]), b"a"));                        // true
    println!("{}", exist(b(&["ab","cd"]), b"abcd"));               // false
}

最优解讲解（通俗版 + 推理过程）

题意翻译：从某个起点格子出发，走上下左右相邻格子，把经过的字符依次拼成 word；同一格子不能重复使用。
为什么这是典型回溯？
- 你每走一步，都要决定“下一步走四个方向里的哪一个”，这是一棵 4 叉的决策树。
- 走到一半发现不匹配，就必须退回上一步换方向（这就是 backtrack）。
状态定义：
- (i,j)：当前所在格子
- k：已经匹配到 word 的第 k 个字符
最关键的两个细节（写错就会 WA）：
1. visited 标记必须是“路径级别”的：同一个格子在同一路径里不能重复用，但换一条路径是可以用的。
  - 所以用“把格子临时改成 #”来表示占用；
  - 递归返回时必须恢复原字符（撤销选择），否则会污染别的起点/别的分支。
2. 剪枝要越早越好：一进函数就判断 board[i][j] !== word[k]，不匹配立刻 return false，别再扩展四个方向。
为什么要从每个格子都试起点？：word 的第一个字符可能出现在任意位置，起点不固定。

类似题目（网格回溯模板：改格子当 visited，再恢复）

tmp = board[i][j]
board[i][j] = "#"
for dir in 4:
  if dfs(next): return true
board[i][j] = tmp

131. 分割回文串

力扣原题：131. 分割回文串

Medium

字符串

动态规划

回溯

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

最优解（回溯 + 回文预处理 DP：O(1) 判断回文）

正在加载编辑器...

Rust 参考（点击展开）

fn partition(s: String) -> Vec<Vec<String>> {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut pal = vec![vec![false; n]; n];
    for i in (0..n).rev() {
        for j in i..n {
            if bytes[i] == bytes[j] && (j - i <= 2 || pal[i + 1][j - 1]) {
                pal[i][j] = true;
            }
        }
    }

    let mut res: Vec<Vec<String>> = vec![];
    let mut path: Vec<String> = vec![];
    fn dfs(
        s: &str,
        pal: &Vec<Vec<bool>>,
        start: usize,
        path: &mut Vec<String>,
        res: &mut Vec<Vec<String>>,
    ) {
        let n = s.len();
        if start == n {
            res.push(path.clone());
            return;
        }
        for end in start..n {
            if !pal[start][end] {
                continue;
            }
            path.push(s[start..=end].to_string());
            dfs(s, pal, end + 1, path, res);
            path.pop();
        }
    }
    dfs(&s, &pal, 0, &mut path, &mut res);
    res
}

fn norm2d(mut v: Vec<Vec<String>>) -> Vec<String> {
    let mut out: Vec<String> = v
        .drain(..)
        .map(|a| a.join("|"))
        .collect();
    out.sort();
    out
}

fn main() {
    println!("{:?}", norm2d(partition("aab".to_string()))); // ["a|a|b","aa|b"]
    println!("{:?}", norm2d(partition("a".to_string()))); // ["a"]
    println!("{:?}", norm2d(partition("aba".to_string()))); // ["a|b|a","aba"]
    println!("{}", norm2d(partition("aaa".to_string())).len()); // 4
    println!("{}", norm2d(partition("racecar".to_string())).contains(&"racecar".to_string())); // true
}

最优解讲解（通俗版 + 推理过程）

题意翻译：把字符串切成若干段，每段都是回文，输出所有切法。
回溯树怎么长（核心建模）：
- 站在位置 start，你要决定“下一刀切到哪里 end”。
- 只要 s[start..end] 是回文，这一刀就合法，递归去处理 end+1。
- 当 start == n，说明刚好切到末尾，path 就是一种完整切法。
性能瓶颈在哪里？：回溯会反复问同一句话：“这段子串是不是回文？”
- 如果每次都现用双指针检查，会在不同分支里重复检查同一段子串，成本很高。
关键优化：先用 DP 把所有回文子串预处理出来：
- pal[i][j] 表示 s[i..j] 是否回文，回溯时直接 (O(1)) 查表。
DP 为什么这样填表（推理顺序）：
- s[i] === s[j] 且内部 s[i+1..j-1] 是回文 ⇒ pal[i][j]=true
- 但这依赖 pal[i+1][j-1]，所以 i 要从右往左枚举（保证内部先算好），j 从 i 往右扩展。
- j-i <= 2（长度 1/2/3）时内部为空或单字符，可直接作为 base case。
小例子："aab"
- a | a | b（每段都是回文）
- aa | b（"aa" 也是回文）
复杂度：DP 预处理 (O(n^2))，回溯输出规模取决于答案数量（最坏指数级），但查回文变成了常数。

类似题目（回溯 + 预处理表：把昂贵判断变成 O(1)）

precompute good[i][j]
dfs(start):
  for end>=start:
    if good[start][end]:
      choose segment
      dfs(end+1)
      undo

51. N 皇后

力扣原题：51. N 皇后

Hard

数组

回溯

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

最优解（回溯：逐行放皇后 + 三个集合剪枝）

正在加载编辑器...

Rust 参考（点击展开）

use std::collections::HashSet;

fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
    let mut res: Vec<Vec<String>> = vec![];
    let mut cols: HashSet<usize> = HashSet::new();
    let mut diag1: HashSet<i32> = HashSet::new(); // r - c
    let mut diag2: HashSet<i32> = HashSet::new(); // r + c
    let mut board = vec![vec![b'.'; n]; n];

    fn dfs(
        r: usize,
        n: usize,
        cols: &mut HashSet<usize>,
        diag1: &mut HashSet<i32>,
        diag2: &mut HashSet<i32>,
        board: &mut Vec<Vec<u8>>,
        res: &mut Vec<Vec<String>>,
    ) {
        if r == n {
            let snap: Vec<String> = board
                .iter()
                .map(|row| String::from_utf8(row.clone()).unwrap())
                .collect();
            res.push(snap);
            return;
        }
        for c in 0..n {
            let d1 = r as i32 - c as i32;
            let d2 = r as i32 + c as i32;
            if cols.contains(&c) || diag1.contains(&d1) || diag2.contains(&d2) {
                continue;
            }
            cols.insert(c);
            diag1.insert(d1);
            diag2.insert(d2);
            board[r][c] = b'Q';
            dfs(r + 1, n, cols, diag1, diag2, board, res);
            board[r][c] = b'.';
            cols.remove(&c);
            diag1.remove(&d1);
            diag2.remove(&d2);
        }
    }

    dfs(0, n, &mut cols, &mut diag1, &mut diag2, &mut board, &mut res);
    res
}

fn main() {
    println!("{}", solve_n_queens(1).len()); // 1
    println!("{}", solve_n_queens(2).len()); // 0
    println!("{}", solve_n_queens(3).len()); // 0
    println!("{}", solve_n_queens(4).len()); // 2
    println!("{}", solve_n_queens(5).len()); // 10
}

最优解讲解（通俗版 + 推理过程）

题意翻译：在 n×n 棋盘上放 n 个皇后，要求任意两个皇后都互不攻击（同列/同对角线都不行；按“逐行放”会天然避免同行冲突）。
为什么按“行”回溯是最优建模？
- 规则里隐含了一个强约束：每一行最多放 1 个皇后（否则同行必冲突）。
- 所以我们把第 r 层定义为“给第 r 行选一个列 c”，这会大幅减少无效状态。
三个集合剪枝是怎么推理出来的？
- 列冲突：同列不能放 → 用 cols 存已占用列 c
- 主对角线冲突：同一条主对角线满足 r-c 相等 → 用 diag1 存 r-c
- 副对角线冲突：同一条副对角线满足 r+c 相等 → 用 diag2 存 r+c
为什么这三类就够了？：皇后的攻击路径只有“竖直”和“两条斜线”，不存在其它方向，所以只要这三类都不冲突，就一定安全。
回溯的撤销动作要配套：
- 放置时：往三套集合里 add + 在棋盘写 Q
- 回退时：从三套集合里 delete + 恢复 .
复杂度直觉：最坏接近 (O(n!)) 的搜索（每行选一列），剪枝会大幅减少实际分支。

类似题目（逐行/逐层回溯 + 集合剪枝）

dfs(row):
  for col in 0..n-1:
    if col/diag conflict: continue
    place; dfs(row+1); remove

回溯（题单顺序）

On this page