每天学一个算法--回溯算法（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(i1)path.pop()7️⃣ 示例3N 皇后重要规则每行一个皇后不能同列不能对角线状态row, col, 对角线本质 在棋盘上逐行尝试8️⃣ 剪枝关键优化什么是剪枝提前终止不可能的路径示例当前和已经 target 不用继续本质减少搜索空间9️⃣ 回溯 vs 动态规划项目回溯DP思路枚举所有记忆优化复杂度高较低是否剪枝有无10️⃣ 时间复杂度通常[O(指数级)][ O(指数级) ][O(指数级)] 但剪枝后会下降常见错误❌ 错误1忘记撤销选择 状态污染❌ 错误2条件写错 多算 / 少算❌ 错误3不会剪枝 变成纯暴力回溯问题分类类型示例排列全排列组合组合数子集子集棋盘问题N皇后路径问题迷宫回溯的本质总结回溯不是“乱试”而是在树上进行有控制的搜索一句话教学总结回溯 “尝试所有可能” “不行就回退”