每天学一个算法--回溯算法（Backtracking）

📘 教案 12：回溯算法（Backtracking · 从暴力到剪枝）

1️⃣ 问题定义

回溯用于解决一类问题：

在所有可能方案中，寻找满足条件的解

典型问题

• 排列 / 组合
• 子集问题
• N 皇后
• 数独
• 路径搜索

2️⃣ 核心思想

回溯 = 系统枚举 + 条件剪枝

本质拆解

• 枚举所有可能（暴力）
• 在过程中排除不合法路径（剪枝）

3️⃣ 回溯的结构模型（最重要）

树形结构（必须理解）

[] / | \ [1] [2] [3] / \ [1,2] [1,3]

👉 每一条路径 = 一个方案

4️⃣ 回溯模板（核心）

defbacktrack(path,choices):if满足条件:保存结果returnfor选择inchoices:做选择 backtrack(path,剩余选择)撤销选择

三个关键动作

1️⃣ 做选择

2️⃣ 递归

3️⃣ 撤销选择（回溯）

👉 这三步必须成对出现

5️⃣ 示例1：全排列（最经典）

问题：

[1,2,3]

求所有排列

解：

defbacktrack(path):iflen(path)==n:res.append(path[:])returnfornuminnums:ifnum 已使用:continuepath.append(num)标记使用 backtrack(path)撤销使用 path.pop()

6️⃣ 示例2：子集问题

问题：

[1,2,3]

求所有子集

关键区别

👉 每个节点都是答案

defbacktrack(start):res.append(path[:])foriinrange(start,n):path.append(nums[i])backtrack(i+1)path.pop()

7️⃣ 示例3：N 皇后（重要）

规则：

• 每行一个皇后
• 不能同列
• 不能对角线

状态：

row, col, 对角线

本质：

👉 在棋盘上逐行尝试

8️⃣ 剪枝（关键优化）

什么是剪枝？

提前终止不可能的路径

示例：

当前和已经 > target

👉 不用继续

本质：

减少搜索空间

9️⃣ 回溯 vs 动态规划

10️⃣ 时间复杂度

通常：

[O(指数级)][ O(指数级) ][O(指数级)]

👉 但剪枝后会下降

常见错误

❌ 错误1：忘记撤销选择

👉 状态污染

❌ 错误2：条件写错

👉 多算 / 少算

❌ 错误3：不会剪枝

👉 变成纯暴力

回溯问题分类

回溯的本质总结

回溯不是“乱试”，而是：

在树上进行有控制的搜索

一句话教学总结

回溯 =
👉 “尝试所有可能”
👉 + “不行就回退”