★ FEATURED ARTICLE 1. 搞懂需求DFS求01串到底在解决什么问题1.1 01串生成问题本质是一棵二叉决策树先对齐一下背景。所谓01串就是长度为n的字符串每个位置只能填0或1比如n3时从000、001、010一直排到111一共2的3次方也就是8个。为什么这里要专门搞一个DFS直接用循环也能把全部情况列出来但在真实刷题或者项目里题目往往不会只让你输出全量01串而是会加上约束最常见的包括相邻位置不能同时为1整个串里恰好有k个1按字典序输出第m个合法串。把01串当成一棵树来看就特别清楚第1位选择0还是1分出两个分支第2位又各自分出两个分支每一层对应串的一个位置。DFS做的事情就是沿着这棵树从根一路走到叶子每走到叶子就得到一个完整串。这样的决策树结构非常自然因为你每深入一层就相当于回答了一个问题这一位填什么而这个问题只依赖前面已经填好的内容不依赖后面还没填的内容。DFS按位置逐个决策的顺序恰好就是这个01串的构造顺序这也是它成为这类题目默认解法的根本原因。1.2 为什么循环枚举在约束面前吃亏有人会问我直接for i in range(1 n)把i转成二进制字符串不也能得到所有01串吗确实在全量枚举的场景下位运算比DFS更简洁。但一旦加了约束循环方案就暴露出两个短板。第一二进制枚举生成的是完整串你必须在生成完之后再写一个check函数从头到尾扫描判断是否满足约束。比如不含连续1每个串都要扫一遍时间复杂度是O(n乘以2的n次方)n稍微大一点就跑不动。第二位运算枚举天然无法利用前缀信息。假设你当前已经确定前几位里出现了连续1那无论后面填什么这个分支都废了。DFS可以在下一层直接return而循环枚举做不到这种中途放弃它仍然会把所有后缀组合都生成完再过滤。表格对比一下方案全量枚举时带约束时剪枝能力二进制位运算循环简洁高效需要事后过滤浪费多无DFS递归回溯模板固定可读性好边生成边判断可在递归入口提前终止分支动态规划/组合数学不适合逐项输出适合只计数不适合列出全部串所以我的结论是如果只要统计数量、n又很大应该去用动态规划或者组合公式但如果题目要求输出所有满足条件的串或者要求按顺序输出第几个串DFS就是最顺手的那把刀剪枝逻辑写在哪、什么时候生效完全由你控制。1.3 这类题适合谁学完能带走什么说实话这个入门门槛不高但价值很高。适合两类人一类是正在补递归和回溯基础的算法初学者另一类是准备机试、笔试需要在短时间内把常见搜索模型稳定写出来的同学。学完这个主题你能带走的不是会写01串这一件事而是一整套DFS状态设计方法边界条件放在哪里、参数怎么选、进入下一层之前要判断什么、回溯时怎么撤销选择。这套方法后续可以直接套到排列、组合、数独、八皇后、子集划分这些搜索题上。我在实际带人的时候发现很多人卡住的不是DFS思路而是递归函数里参数太多不知道哪个该传、哪个该用全局变量。接下来我会从最朴素的全量枚举开始逐步把参数设计和剪枝逻辑讲清楚最后再通过三个实战场景把知识落地。2. 核心模板三步写出可剪枝的DFS生成框架2.1 最简模型先把长度为n的全量01串跑出来不管题目最后问什么我都建议先写一个最裸的生成器给定n输出所有长度恰好为n的01串。这一步的目的是把递归框架跑通排除递归边界写错状态污染这类低级问题。直接上代码def dfs_all(n, pos, path): if pos n: print(.join(path)) return path.append(0) dfs_all(n, pos 1, path) path.pop() path.append(1) dfs_all(n, pos 1, path) path.pop() dfs_all(3, 0, [])这段代码的核心逻辑只有三部分。第一部分是边界条件当pos等于n时说明每一位都已经确定路径里的字符凑成了一个完整串此时输出并返回。第二部分是枚举当前位填0把0追加到path末尾递归处理下一位。第三部分是枚举当前位填1过程同上。这里绝不能被两行代码长得一样骗过去这其实就是二叉树的两个分支先走左边再走右边天然形成字典序。你可能注意到我在每个分支之后都调用了一次path.pop()这叫恢复现场。为什么必须恢复假设你走完左分支path末尾多了一个0如果不把它弹掉下一轮右分支初始化的时候path里就多了一个不属于当前状态的字符最终输出的串全部错乱。初学者最容易漏掉这一步于是结果串越拼越长。如果不想手动管理path的增删也可以把path改成字符串传参def dfs_all_str(n, pos, s): if pos n: print(s) return dfs_all_str(n, pos 1, s 0) dfs_all_str(n, pos 1, s 1)字符串是不可变对象每次递归传入的是新字符串原变量不会被修改天然不需要pop。这种写法更安全但在n较大、需要反复拼接时会有复制开销。我的习惯是n小于等于20时怎么方便怎么来n更大时用list加pop减少字符串拷贝。2.2 状态放参数还是放全局变量我的选型经验接下来这个问题很关键递归函数里要记录的当前状态到底该放参数还是放全局变量我见过不少同学把path、count、last这些统统定义成全局变量然后在递归函数里用global关键字修改最后十个bug有八个都是从这来的。我的经验是能用参数传的就用参数传。原因很简单参数是函数调用栈上独立的一份值每一层递归自然拥有自己那刻的快照分支之间互不干扰。比如场景一的上一位填了什么直接作为last参数传下去进入0分支时传last0进入1分支时传last1根本不需要在回溯时手动复位。而全局变量是同一份内存你必须在递归返回前手动恢复原值否则当前层的修改会泄漏到其他分支。什么时候必须用全局变量只有两种情况一是需要维护一个结果集list用来收集所有完整串二是需要计数器统计一共生成了多少个合法串。这种收集/计数的变量可以定义在外层因为每个分支都往同一个列表里添加内容是安全的不会污染搜索状态。但凡是跟当前分支走到哪了相关的信息比如当前串、当前1的数量、上一位的值我全部通过参数传递。一句话总结状态跟着递归走结果跟着全局走。这样写出来的代码回溯时几乎不需要做什么额外操作思路清晰调试的时候也容易定位。2.3 剪枝不是优化而是让DFS可用的前提很多教材把剪枝说成性能优化技巧好像不剪枝也能跑只是慢一点。但在01串相关题目里剪枝往往不是优化而是让程序在合理时间内出结果的必要条件。原因很简单全量01串有2的n次方个n30就已经超过10亿任何一台普通机器都不可能遍历完。可一旦有了约束很多分支在很浅的位置就能判定死路剪枝可以把指数级的搜索空间压缩成合法方案数级别。剪枝的基本写法是在递归函数的开头加判断发现当前前缀不可能走向合法解就直接return。常见的剪枝类型总结成三类非法前缀剪枝当前已经违反了题目约束比如出现了连续1后面不用再搜。数量超限剪枝当前累计的1已经超过k个后面就算全填0也无法弥补。剩余能力剪枝当前1太少了就算后面所有位置全填1也凑不够k个同样没希望。以恰好k个1为例两个剪枝条件缺一不可。第一句话if cnt k: return处理的是超限第二句话if n - pos k - cnt: return处理的是不足。前者很直观后者则是很多人会漏掉的关键点——它利用剩余位置数和还差多少个1进行比较如果剩余位置已经少于需要补齐的数量直接放弃。剪枝写得好不好决定了程序是在复杂度可控的搜索树上走还是在满二叉树里瞎逛。后面三个实战场景会让你更直观地感受到这一点。3. 三个实战场景把DFS从会跑练到好用3.1 场景一不含连续1的01串选1前看一眼last第一个经典场景求长度为n、且任意相邻两位不同时为1的所有01串。这道题的DFS解法非常直观每一位选0一定合法因为选0不会制造连续1选1之前看一眼上一位如果上一位是1那么这一位再填1就会形成11必须跳过。代码如下def dfs_no11(n, pos, path, last): if pos n: print(.join(path)) return path.append(0) dfs_no11(n, pos 1, path, 0) path.pop() if last ! 1: path.append(1) dfs_no11(n, pos 1, path, 1) path.pop() dfs_no11(4, 0, [], 0)这里last参数就是上一位的值初始为0因为第1位前面没有限制你可以看成前一位是0。为什么只要判断last ! 1就行因为不含连续1唯一的非法场景就是当前位选1且前一位也是1没有其他组合会出问题。这个题还有个有意思的地方合法串的数量不是2的幂而是斐波那契数列。我列几个n对应的数量n合法01串数量为什么是这个规律120、1都合法2300、01、1035000、001、010、100、10148从n3合法串末尾加0或满足条件加1得到你会发现从n3开始数量等于前两项之和这就是斐波那契数列的递推。明白这个规律有什么用它可以用来验证你的DFS有没有漏解。我每次写完递归都会用这个数量关系做一次交叉检查n5时合法串应该是13个如果程序输出14个说明恢复现场或者判断条件出了问题。如果你打算用循环枚举再过滤n30时全量是10亿个串而合法串大约只有217万个两者差了三个数量级。这就是剪枝带来的真实差距。3.2 场景二恰好k个1两个剪枝条件缺一不可第二个场景更偏计数类列出所有长度为n、且恰好包含k个1的01串。比如n4、k2时答案应该是0011、0101、0110、1001、1010、1100这六个其实就是从4个位置里选2个放1的组合问题。DFS实现时可以维护一个cnt表示当前已经用了几个1目标值k作为全局参数传下去。核心代码长这样def dfs_k_ones(n, k, pos, cnt, path): if cnt k: return if n - pos k - cnt: return if pos n: print(.join(path)) return path.append(0) dfs_k_ones(n, k, pos 1, cnt, path) path.pop() path.append(1) dfs_k_ones(n, k, pos 1, cnt 1, path) path.pop()第一个剪枝if cnt k: return处理的是当前1已经超过目标的情况。这个判断放在所有递归入口之前确保一旦超限整棵子树全部跳过。第二个剪枝if n - pos k - cnt: return是最容易被忽略的它的意思很直白现在还剩下n-pos个位置没填但我还需要k-cnt个1如果剩下的位置数量已经小于需要的1数量说明这个分支无论如何也凑不够目标了。为什么两个剪枝都写了才算完整只写第一个剪枝程序能避免超限但仍然会大量探索1太少的分支比如n10、k9前面填了大量0程序会把很多明显不可能的分支走到很深层才发现凑不够。只写第二个剪枝又会出现cnt已经超过k但还没有被拦截的情况因为第二个条件是用不够来判断的超限时它不会触发。所以这类题最稳妥的做法就是把超限和不够两把剪刀都放在门口一个管住上限一个管住下限。还要注意dfs_k_ones的边界顺序应该先做剪枝判断再做pos n的输出判断。如果把输出判断放在剪枝前面会出现一种bug当pos等于n但cnt还没达到k时程序也会把这个不合法串输出而正确逻辑应该是不满足条件就不输出。初学时要养成习惯剪枝永远优先于收尾判断。3.3 场景三字典序第K小用子树计数直接跳过第三个场景稍微进阶一点不是列出所有合法01串而是要求输出所有串中字典序排在第m位的那个。比如同样是不含连续1的长度为4的01串按字典序排分别是0000、0001、0010、0100、0101、1000、1001、1010第5个就是0101。最笨的办法是DFS把所有串都生成出来存到列表里最后取第m个。但这样做了大量无用功因为前m个之前的串必须全部生成后面的串也全部浪费了。更好的办法是在DFS过程中引入子树计数每一层都知道当前状态下继续搜下去还能得到多少个合法方案如果这个数量大于等于剩余的需求就走这个分支如果小于剩余需求就把需求量减掉这个数量然后跳过这个分支。具体来说每次进入一个分支之前先估算这个分支能贡献多少合法串。比如不含连续1的状态中如果当前last0下一位填0和1都合法如果last1则只有下一位填0合法这些可以预先算出来。更通用的做法是用一个递归函数count(pos, state)返回从这个状态出发还能生成的合法串数量再在找第m个的过程中调用它做决策。伪代码类似这样def kth_smallest(n, k, pos, last, need, path): if pos n: return True # 先尝试填0 zero_cnt count_ways(pos 1, 0, n, last) if need zero_cnt: path.append(0) if kth_smallest(n, k, pos 1, 0, need, path): return True path.pop() else: need - zero_cnt # 再尝试填1这里的前提是当前fill 1合法 path.append(1) if kth_smallest(n, k, pos 1, 1, need, path): return True path.pop() return Falsecount_ways返回的是一个数值它可以提前用DP算好也可以再用一个不带输出、只计数的DFS来算。这么做的好处是你不需要遍历完整棵搜索树每层只走一个分支最多走n层就得到答案时间复杂度从指数级降到近似多项式级。对n较大、只想要第m个结果的场景这个优化非常关键。初学者建议先把前两个场景练熟再挑战这个。因为子树计数本质上是你对搜索树结构理解的体现你能画出每个状态的子树规模才算真正掌握了DFS的剪枝思路。4. 常见问题与排查技巧DFS跑偏时我都是这么定位的4.1 忘恢复现场输出串越拼越长这个是我见过最频繁的bug没有之一。症状很典型输出的一堆结果串长度参差不齐有的长有的短甚至同一个串重复出现多次。原因就是直接在path.append之后就递归返回忘了在递归之后调用path.pop()或者path path[:-1]复位。举个例子你搜所有长度为3的01串如果填0分支结束后没有把末尾的0弹掉进入填1分支时path其实是[0]而不是空列表最后输出的串就会比正确的多一个前缀甚至多出几个字符。定位方法不难在每次递归调用前打印当前path和pos你会看到上一层残留的字符混进了下一层。修复方式有两个要么严格成对地写append和pop要么把path改成字符串参数直接拼接省去手动复位。我建议从字符串版本开始理解理解后再切换到list版本追求性能这样不容易被恢复现场的细节绊倒。4.2 剪枝条件写错一位漏解到怀疑人生剪枝条件写错往往不会导致程序崩溃而是闷声让你产出错误的答案。举个例子恰好k个1的题里如果我把超限判断if cnt k误写成if cnt k那么在当前cnt已经等于k但还有位置没填完时程序会立刻返回把所有后续合法分支全部砍掉而实际上cnt等于k时只是不能再填1了仍然可以继续填0把串补完。类似的还有判断剩余位置不够时把k - cnt写反变成cnt - k结果永远不满足条件程序直接什么都不输出。遇到这种答案少了的情况我的排查步骤是先用小n暴力枚举一遍确定标准答案。在递归函数入口打印pos、cnt、last等参数观察剪枝触发的位置。对照剪枝条件逐一推理看是不是边界写死、方向写反。用数量关系做交叉验证比如斐波那契数列、组合数C(n,k)等。强烈建议在写完任何带剪枝的DFS后输出一个Counting计数器把最终合法方案的总数统计出来跟理论值比对。这比肉眼看输出列表靠谱得多。4.3 超时和栈溢出先确认DFS的适用边界不是所有01串问题都该用DFS硬顶。前面说过n20时全量枚举100万级别没问题n30时全量10亿级别纯DFS即使剪了一些分支也很悬。如果题目给的n在50甚至100以上又要统计合法方案总数正确的方向是动态规划或者组合数学而不是递归搜索。Python默认的递归深度上限一般是1000对01串DFS来说十进制的n一般不会超过100所以栈深度通常不会爆。但如果你在递归里套了多层循环或者把DFS封装成类方法、每次构造大对象可能会遇到递归深度相关的报错。这时可以先用sys.setrecursionlimit提高上限同时检查递归终止条件是否真的会在合理深度触发。另外有个经验之谈DFS跑得慢不一定是因为剪枝不够有可能是你在每个节点做了大量重复计算比如反复对同一个list做拼接、频繁创建新字符串。如果n在20到30之间建议用list加回溯而不是字符串拼接如果n超过30趁早换思路。4.4 问题速查自检表我把高频问题汇总成一张速查表方便你写完代码后逐项检查现象最常见原因定位方法快速解决输出串长度不一恢复现场缺失在递归入口打印当前path成对写append/pop输出重复串全局变量在分支间残留打印每次进入递归前的状态状态全部改参数传递正确方案数量偏少剪枝条件过强用小n对照暴力结果逐条检查边界符号正确方案数量偏多剪枝条件没生效在剪枝处加打印确认剪枝在合法位置程序没有输出边界条件顺序颠倒打印pos变化剪枝判断放在输出判断之前运行超时剪枝不足或n过大统计访问节点数增加剪枝或换DP思路每次写完搜索类题目我都习惯按照这个表过一遍。宁可多花两分钟检查也不要在提交之后被测试用例教做人。最后再分享一个小习惯我拿到任何DFS求01串类型的题目第一步永远先写最裸的枚举代码用n3或者n4确认框架正确第二步只加题目要求的那一行核心剪枝验证合法串数量第三步才考虑字典序、第k小这类附加需求。分阶段推进出了bug也能立刻判断是哪一步引入的。这套方法不只适用于01串凡是在决策树上做搜索的题目都可以用同样的节奏写。
阅读完成 · 觉得有帮助？
