【每日一题】回溯法

一、回溯法基础DFS的进阶形态1.1 什么是回溯法回溯法 DFS 状态标记 剪枝策略核心特征本质上是DFS的一种在搜索尝试过程中寻找问题的解发现不满足条件时立即回溯不继续深入无效分支走过的路需要打标记vis数组防止重复使用回溯时清除标记恢复状态供其他路径使用1.2 回溯 vs 普通DFS对比项普通DFS回溯法状态标记一般不需要必须打标记适用场景组合枚举、数值拆分排列、子集、棋盘问题核心操作递归深入标记→递归→清除标记典型问题n重循环替代全排列、N皇后、子集和1.3 两种经典的回溯树排列树每个节点的子节点是所有未被选择的元素例如1,2,3的全排列第一层选1/2/3第二层选剩下两个第三层选最后一个子集树每个节点有两个分支——选或不选当前元素例如{1,2,3}的所有子集每个元素都有选和不选两种选择二、回溯模板求排列2.1 问题描述输出1~n的所有全排列。2.2 核心思路排列要求数字不重复——每次选择的数字需要打标记——vis数组要输出当前排列——记录路径——path数组回溯流程先打标记、记录路径、然后下一层、回到上一层、清除标记2.3 代码实现defdfs(depth):# 当前为第depth个数字0到depth-1已经设置好ifdepthn:print(path)return# 枚举第depth个数字foriinrange(1,n1):# 数字i必须先前未选择ifvis[i]isFalse:# 标记当前状态vis[i]True# 记录当前路径path.append(i)# 进行下一层搜索dfs(depth1)# 清除标记回溯vis[i]Falsepath.pop(-1)nint(input())path[]vis[False]*(n1)dfs(0)2.4 关键理解为什么需要回溯清除标记假设n3当前path[1]进入dfs(1)后在第二层选择了2path[1,2]然后进入dfs(2)选择3输出[1,2,3]。返回后需要清除3的标记然后尝试第二层选3得到[1,3,2]。当第二层所有选择都尝试完后返回第一层需要清除1的标记然后第一层选2开始生成以2开头的排列。如果不清除标记1永远被标记为True后面就无法生成以2或3开头的排列了三、回溯模板求子集3.1 问题描述给定n个数字输出所有子集。3.2 核心思路每个元素只有两种状态选或不选。用DFS枚举这两种选择即可。3.3 代码实现nint(input())alist(map(int,input().split()))path[]defdfs(depth):ifdepthn:print(path)return# 选当前元素path.append(a[depth])dfs(depth1)path.pop(-1)# 回溯# 不选当前元素dfs(depth1)dfs(0)3.4 关键理解子集问题比排列问题简单因为不需要vis数组元素按顺序处理不会重复每个元素只有两种选择天然适合DFS叶子节点depthn就是一个完整的子集选与不选的顺序先选后不选或者先不选后选都可以只是子集输出的顺序不同。四、实战演练N皇后 经典回溯 多标记数组题目链接蓝桥杯1508题目描述在N×N的方格棋盘放置N个皇后使它们不相互攻击即任意2个皇后不允许处在同一排、同一列也不允许处在与棋盘边框成45°角的斜线上。求有多少种合法的放置方法。核心思路DFS枚举每一行放置的列需要标记三种冲突列、主对角线、副对角线对角线的巧妙标记主对角线x y为定值从左上到右下副对角线x - y n为定值从右上到左下加n避免负数defdfs(depth):# 当前为第depth行0到depth-1行已经设置好ifdepthn:globalans ansans1return# 枚举第depth行放在哪列foriinrange(1,n1):# 坐标为(depth, i)# 第i列先前未选择、主对角线未选择、副对角线未选择ifvis1[i]isFalseandvis2[depthi]isFalseandvis3[depth-in]isFalse:# 标记当前状态vis1[i]Truevis2[depthi]Truevis3[depth-in]Truedfs(depth1)# 清除标记回溯vis1[i]Falsevis2[depthi]Falsevis3[depth-in]Falsenint(input())ans0vis1[False]*(n1)# 列标记vis2[False]*(2*n1)# 主对角线标记 (xy)vis3[False]*(2*n1)# 副对角线标记 (x-yn)dfs(0)print(ans)复杂度时间O(n!)空间O(n)关键细节depth表示当前处理第几行从0开始i表示当前行放在第几列从1开始三个vis数组分别标记列、主对角线、副对角线vis2和vis3的大小为2*n1因为xy最大为2nx-yn的范围是0~2n回溯时必须三个标记同时清除否则状态不一致为什么按行枚举因为每行只能放一个皇后按行枚举天然保证了不在同一行的约束只需要判断列和对角线即可。如果按格子枚举代码会更复杂且效率更低。五、回溯法专题应用场景总结应用场景回溯技巧时间复杂度代表题目全排列vis标记 path记录O(n!)全排列问题子集枚举选/不选两种分支O(2^n)子集和问题组合枚举vis标记 限制选择范围O(C(n,k))组合数问题棋盘放置多维度标记数组O(n!)N皇后路径搜索vis标记 方向数组O(4^n)迷宫问题数独求解行/列/宫三维标记O(9^m)数独六、回溯法的核心要点6.1 回溯三要素路径记录已经做出的选择path数组选择列表当前可以做的选择for循环枚举结束条件到达决策树底层无法再做选择depth n6.2 回溯代码框架defbacktrack(路径,选择列表):if满足结束条件:记录结果returnfor选择in选择列表:if选择不合法:continue# 做选择路径.add(选择)标记选择为已使用# 进入下一层决策树backtrack(路径,新的选择列表)# 撤销选择回溯路径.remove(选择)清除标记6.3 常见问题与调试技巧问题1忘记清除标记现象输出结果不完整或者进入死循环解决检查dfs(depth1)之后是否有对应的清除操作问题2标记数组大小不够现象数组越界或标记冲突解决仔细分析标记的取值范围如N皇后的对角线标记问题3递归出口条件写错现象结果多算或少算解决depth从0开始时出口是depth n从1开始时出口是depth n七、结语回溯法的魅力在于通过标记-递归-清除标记的套路优雅地解决排列、组合、棋盘等复杂问题。掌握回溯模板后N皇后、全排列、子集和等问题都能迎刃而解。学习建议先理解为什么要回溯——如果不回溯状态会被污染无法尝试其他路径熟记回溯模板标记→递归→清除标记三个步骤缺一不可从全排列入手理解vis数组的作用再扩展到子集、N皇后N皇后的对角线标记是经典技巧xy和x-yn要理解其原理多动手画图画出递归树和回溯过程加深理解如果本文对你有帮助欢迎点赞 收藏 关注你的支持是我持续更新的动力有问题欢迎在评论区交流看到都会回复的