回溯算法（Backtracking）

更加完整详细内容可查看【免费版Java学习笔记】和【免费版Java面试题】

免费版Java学习笔记（28w字）链接：https://www.yuque.com/aoyouaoyou/sgcqr8 免费版Java面试题（20w字）链接：https://www.yuque.com/aoyouaoyou/wh3hto 完整版Java学习笔记200w字，附有代码实现，图解清楚，仅需9.9 完整版Java面试题，150w字，高频面试题，内容详细，仅需9.9 完整版链接： https://www.xiaohongshu.com/user/profile/63c2d512000000002601232c 祝您新的一年事事马到成功，身体健康，阖家幸福，大展宏图！

一、回溯算法介绍

1.1 算法定义

回溯算法是一种带“回退”的深度优先搜索枚举算法，是在问题求解的多阶段尝试过程中，从一条路径探索解，当发现当前路径不满足求解条件时，就回溯（递归返回）到上一个决策点，放弃当前路径并尝试其他可能的路径，直到找到满足要求的解或枚举完所有可能。

简单来说，回溯的解题逻辑是：一路向前试，走不通就回头，换条路再试，像走迷宫时遇到死胡同，退回最近的岔路口选另一个方向。

1.2 思想：多阶段决策+回退剪枝

回溯把问题求解拆分为多个有序的决策阶段，每个阶段面对多个选择，操作可概括为：

1.3 与深度优先搜索（DFS）的关系

回溯是特殊的DFS，二者都基于深度优先的探索逻辑，但回溯多了“回退”和“剪枝”的特性：

• DFS：仅做深度优先的遍历，不关注路径是否符合解的条件，遍历完成即结束；
• 回溯：以DFS为基础，遍历中加入条件判断，不符合则回退，还可通过剪枝减少遍历次数，目标是找到符合要求的解而非单纯遍历。

此处为语雀内容卡片，点击链接查看：https://www.yuque.com/aoyouaoyou/pbz18g/riiovgtq5us3og5c

二、回溯算法的经典问题：N皇后问题

N皇后问题是回溯算法的经典标杆问题，能完美体现“多阶段决策+尝试+回溯+剪枝”的逻辑。

2.1 问题描述

在n×n的棋盘上放置n个皇后，要求皇后彼此之间不能相互攻击，即任意两个皇后不能出现在同一行、同一列、同一对角线上，求所有合法的放置方案。

• 规则：皇后的攻击范围是所在行、列、左上/右下对角线；
• 阶段划分：将问题拆分为n个阶段，依次在第1行、第2行……第n行放置皇后（每行仅放1个，天然避免同一行攻击，简化问题）；
• 决策选择：每个阶段（第row行）的选择是在第0列到第n-1列中选一个列col放置皇后；
• 条件判断：放置前检查第row行col列是否与已放置的皇后冲突（不同列、不同对角线）。

2.2 解题思路

2.3 冲突判断逻辑（关键）

对第row行col列，只需向上检查已放置的0~row-1行（后续行未放置，无需检查），判断三个维度：

2.4 完整代码实现（支持自定义皇后数）

代码优点：① 皇后数可自定义（通过常量配置）；② 简化冲突判断逻辑；③ 增加方案计数：

/**
* 回溯算法：N皇后问题（优化版，支持自定义皇后数）
* 行作为阶段，列作为选择，冲突判断后递归，无效则回溯
*/
public class AoyouBacktrackingNQueens {
// 自定义皇后数（示例：8皇后/4皇后，可修改）
public static final int QUEENS = 8;
// 存储皇后位置：result[row] = col → 第row行皇后放在第col列
private int[] result = new int[QUEENS];
// 统计合法方案数
private static int solutionCount = 0;

/**
* 回溯方法：在第row行放置皇后（多阶段决策的）
* @param row 当前处理的行（阶段）
*/
public void setQueens(int row) {
// 递归终止条件：row == QUEENS，说明所有皇后已合法放置，找到一个解
if (row == QUEENS) {
solutionCount++;
printQueens(); // 打印当前合法方案
return;
}

// 遍历当前行的所有列（当前阶段的所有选择）
for (int col = 0; col < QUEENS; col++) {
// 剪枝：判断当前row行col列是否可放置（无冲突则尝试，有冲突则跳过该列）
if (isOk(row, col)) {
result[row] = col; // 记录当前选择：第row行皇后放在col列
setQueens(row + 1); // 进入下一个阶段：处理下一行
// 回溯操作（隐式）：递归返回后，自动尝试当前行的下一个col，无需额外代码
}
}
// 若当前行所有列都尝试完毕仍无合法位置，递归返回（回溯到上一行）
}

/**
* 辅助方法：判断第row行col列是否可放置皇后（冲突判断+剪枝）
* @param row 当前行
* @param col 当前列
* @return true=可放置，false=不可放置
*/
private boolean isOk(int row, int col) {
// 向上遍历已放置的所有行（0 ~ row-1），检查冲突
for (int i = 0; i < row; i++) {
// 1. 同列冲突：已放置的皇后在当前列
if (result[i] == col) {
return false;
}
// 2. 对角线冲突：行差的绝对值 == 列差的绝对值（统一判断左上/右下对角线）
if (Math.abs(row – i) == Math.abs(col – result[i])) {
return false;
}
}
// 无冲突，可放置
return true;
}

/**
* 辅助方法：打印当前合法的皇后放置方案
*/
private void printQueens() {
System.out.println("========== 合法方案" + solutionCount + " ==========");
for (int row = 0; row < QUEENS; row++) {
for (int col = 0; col < QUEENS; col++) {
if (result[row] == col) {
System.out.print("Q | "); // 皇后位置
} else {
System.out.print("* | "); // 空位置
}
}
System.out.println(); // 换行到下一行
}
}

// 测试主方法（示例：8皇后/4皇后，修改QUEENS常量即可切换）
public static void main(String[] args) {
AoyouBacktrackingNQueens nQueens = new AoyouBacktrackingNQueens();
nQueens.setQueens(0); // 从第0行开始放置皇后
System.out.println("=====================================");
System.out.println(QUEENS + "皇后问题的总合法方案数：" + solutionCount);
}
}

2.5 运行结果（以4皇后为例，QUEENS=4）

4皇后问题共有2个合法方案，运行结果如下：

========== 合法方案1 ==========
* | Q | * | * |
* | * | * | Q |
Q | * | * | * |
* | * | Q | * |
========== 合法方案2 ==========
* | * | Q | * |
Q | * | * | * |
* | * | * | Q |
* | Q | * | * |
=====================================
4皇后问题的总合法方案数：2

（8皇后问题共有92个合法方案，运行代码可完整打印所有方案）

2.6 时间复杂度分析

N皇后问题的时间复杂度为指数级别，这是回溯算法的典型特征：

• 最坏情况：每个行有n个列选择，共n行，时间复杂度为；
• 实际情况：通过冲突判断剪枝，大部分路径会被提前终止，实际时间复杂度远低于，但仍为指数级（如8皇后仅需枚举约1.5万次，而非次）。

结论：回溯算法的时间复杂度通常为

（k为每个阶段的选择数），属于暴力枚举的范畴，仅适合解决小规模数据问题。

三、优缺点

3.1 优点

3.2 缺点

四、适用场景

回溯算法是“万金油”，但因时间复杂度限制，主要适用于小规模数据的搜索/枚举类问题，尤其适合解决需要找到所有解/最优解的场景，经典适用场景可分为4类：

4.1 排列组合类问题

从一组数据中选择若干元素，求所有满足条件的排列/组合/子集，如：

• 全排列问题：求1~n的所有排列方式；
• 组合求和：从数组中选若干元素，和为目标值的所有组合；
• 子集问题：求一个数组的所有子集。

4.2 棋盘类问题

基于棋盘的多阶段决策问题，如：

• N皇后问题（经典）；
• 数独问题：填充数独棋盘，满足行、列、3×3宫格无重复数字；
• 马踏棋盘：马从棋盘某点出发，走遍所有格子且仅走一次。

4.3 路径探索类问题

寻找符合条件的路径，如：

• 迷宫问题：从迷宫起点到终点的所有合法路径；
• 单词搜索：在二维字符网格中寻找指定单词的所有路径。

4.4 优化选择类问题

从所有可能的解中筛选最优解（小规模数据），如：

• 0-1背包问题（小规模n）：求背包能装的最大价值（大规模需用动态规划）；
• 旅行商问题（小规模城市数）：求访问所有城市的最短路径。

适用原则：当问题的数据规模小（n≤20），且需要找到所有解/最优解时，优先选择回溯算法；若数据规模大，则需考虑动态规划/贪心。

五、回溯算法与动态规划/贪心的对比

回溯、动态规划、贪心都是解决多阶段决策问题的常用算法，但三者的解题思路、效率、适用场景差异极大，从5个维度对比，快速区分选型：

六、实现技巧

6.1 明确阶段与选择

将问题拆分为有序的多阶段，明确每个阶段的所有可选路径，这是回溯的基础（如N皇后以“行”为阶段，以“列”为选择）。

6.2 巧用递归实现回退

回溯的回退操作无需额外代码，递归的“栈帧”会天然保存上一阶段的状态：递归进入下一个阶段时，当前阶段的选择会被保存；递归返回时，自动回到上一阶段，尝试下一个选择（如N皇后中，setQueens(row+1)返回后，自动遍历当前行的下一个col）。

6.3 剪枝优化

剪枝是提升回溯效率的关键，是在尝试路径前预判无效，直接跳过该路径的所有后续探索，常见剪枝方式：

• 条件剪枝：如N皇后的冲突判断，提前跳过无法放置的列；
• 边界剪枝：如组合求和中，当前和已超过目标值，直接跳过后续选择；
• 有序剪枝：将数据排序后，跳过重复的选择，避免生成重复解。

七、总结