回溯算法综合练兵：组合总和、优美排列与状态机详解

很多人学完递归就卡在回溯原因只有一个递归只需要一路向前回溯还要学会高明的“后悔”。本次专题五正好到了综合练兵的中段我用三个经典的搜索问题——组合总和、优美排列、状态机——把回溯的剪枝、计数和状态表达练一遍。如果你已经理解递归的模板但对“什么时候撤销、怎么去重、怎么把状态压缩成数字”还一头雾水这篇内容就是给你准备的。三个问题难度刚好递进组合总和练最基础的“选与不选”优美排列练“合法条件筛选”状态机则把视角拉高到状态转移是后面做复杂搜索和动态规划的跳板。1. 回溯算法的核心套路与专题设计思路1.1 回溯三步法选择、约束、撤销回溯本质是在一棵隐式的决策树上做深度优先遍历。每到一个节点你要做三件事确定当前可选范围、判断当前选择能不能做、做完之后把状态还原。大多数人写不出回溯不是不懂递归而是忘了“还原现场”。我用最朴素的语言描述这个模板先准备一个容器path装中间结果再写一个dfs函数函数里先判断是否到达终止条件然后遍历候选值如果当前值满足约束就把它加入path递归处理下一层递归返回后立刻从path里弹出这个值恢复成选择前的样子。“撤销”这一步最容易被忽略。假设你用一个全局数组记录已访问的元素如果不撤销下一层分支看到的状态就是被污染过的会漏掉大量正确答案。你可以把撤销理解为给递归分支发了一颗“后悔药”当前分支探索完必须把环境恢复原状让兄弟分支从同一个起点出发。实际操作中我习惯把“加入选择”和“撤销选择”成对写在递归调用的前后中间只有一行递归语句。这样代码结构一眼就能看清不会出现漏撤销或撤销位置错误的问题。1.2 为什么拿这三个问题当综合大练兵专题五这套组合题是我反复比较后留下的。组合总和是回溯最经典的“无限可重复取”场景能练到剪枝和去重优美排列是典型的计数型回溯难度在合法条件判断和预处理状态机则是把一组候选状态抽象成二进制位练的是对搜索空间的理解。三道题合在一起刚好覆盖回溯的三种重要能力控制搜索范围、过滤非法分支、压缩状态表达。第一个问题练的是“位置概念”。组合总和里元素可以重复使用如果稍不注意就会产生重复组合需要用索引单调递增来约束方向。第二个问题练的是“条件判定”。优美排列要求每一个位置上的数字和位置之间满足整除关系搜索时每次都要检查大量组合能不能提前建好合法关系表直接影响运行时间。第三个问题练的是“状态抽象”。当排列或子集的状态很多时用布尔数组、字符串、元组都不如位运算简洁状态机视角让我们把每一步看成“当前状态一个决策新状态”。这三个问题若只靠背模板是无法一次写对的。组合和的去重条件、优美排列的预处理、状态机的位掩码全都有各自的坑。把它们放在同一篇里逐个攻克后面遇到实际项目中的路径规划、任务分配、配置组合等搜索问题心里会更有底。2. 组合总和从“无限可取”到“去重剪枝”2.1 第一版全量搜索的直觉写法先看最朴素版本。给一个正整数数组candidates一个目标值target要求返回所有组合使得组合中数字之和等于target。数组里的数字可以无限重复使用组合之间不能重复。直觉写法如下每次递归都从头开始遍历数组选择当前数字后因为可以重复使用所以下一层仍然从当前位置开始搜索。def combination_sum(candidates, target): res [] path [] def dfs(start, remain): if remain 0: res.append(path[:]) return if remain 0: return for i in range(start, len(candidates)): path.append(candidates[i]) dfs(i, remain - candidates[i]) # 重点还传i允许重复取 path.pop() dfs(0, target) return res这个代码能跑通不重复的基本用例但有一个隐藏问题如果candidates里有重复数字结果中会出现重复组合。先记住这一点后面专门处理。“还传i”是无限可重复取的精髓。假如改成dfs(i 1, ...)当前元素就不能再被选相当于变成了“每个数字最多用一次”的组合问题。很多初学者在这个参数上犯迷糊其实只要想清楚下一层可选的起始位置是i还是i1就决定了元素能不能复用。另一个容易忽略的是remain这个参数。我没有每次去算sum(path)而是把目标值递减递归进入下一层时直接判断正负。这样省去了求和操作也让终止条件更直观。如果remain已经小于0说明当前路径已经超出目标直接return不需要继续往下搜。2.2 剪枝策略排序、跳过重复、上限判断当输入数组中有重复数字且每个数字只能使用一次时问题变成组合总和的一个常见变体。必须先对数组排序原因有两个一是让相同数字相邻方便后续去重二是可以提前结束循环当前数字如果大于剩余目标值后面的数字只会更大直接break。下面给出可以输出不重复组合的写法def combination_sum_no_repeat(candidates, target): candidates.sort() res [] path [] def dfs(idx, remain): if remain 0: res.append(path[:]) return for i in range(idx, len(candidates)): # 同一层递归中跳过已经用过的相同数字 if i idx and candidates[i] candidates[i - 1]: continue # 数字已经比剩余目标值大后续更大直接退出 if candidates[i] remain: break path.append(candidates[i]) dfs(i 1, remain - candidates[i]) path.pop() dfs(0, target) return res去重条件i idx and candidates[i] candidates[i - 1]是这段代码里最值得细看的点。它只跳过“同一层递归”中的重复不会跳过不同层递归中的重复。举个例子数组是[1, 1, 2]目标值是3我们要得到[1, 2]两个1都可能被选成第一个元素但只能产生同一个组合。如果不加i idx条件第二个1在第一个位置时会被误杀导致正确组合丢失。我刚开始学的时候会把条件写成i 0 and candidates[i] candidates[i-1]结果所有包含重复数字的正确组合都被过滤掉了。后来才明白i idx限制的是“在当前这一层分支内同一个数字只作为第一个候选尝试一次”而不是全局禁用重复值。2.3 复杂度分析与参数选择心得组合总和的时间复杂度在最坏情况下是指数级因为搜索空间本身就是组合爆炸的。剪枝能减少一部分分支但无法改变最坏复杂度。实际操作时我会先分析递归深度在无限可取版本中最大深度是target / min(candidates)在不可重复版本中最大深度是数组长度。了解这个才能预判数据规模多大时需要额外剪枝或改成动态规划。参数设计直接影响代码简洁度。我强烈建议把“当前剩余目标值”作为函数参数而不是每层重新计算总和。原因很简单每做一次选择remain减去选中的数递归返回后remain的值自动恢复因为它作为参数传进去的是副本不需要手动还原。这比维护一个全局sum变量来得安全。我还习惯把candidates数组的长度放进循环范围判断但不在循环体内反复取len()如果需要频繁用先存成局部变量。不要小看这些细节当数组长度上千、搜索分支多的时候这些微小的性能差异会被放大。3. 优美排列让回溯学会“动态合法集”3.1 题目解读与状态定义优美排列是一道很有意思的计数回溯题。给定整数n要求统计所有排列P[1..n]的数量满足对于每个位置i要么i能被P[i]整除要么P[i]能被i整除。也就是说位置和数字必须存在整除关系。可以把问题理解成“给每个位置安排一个还没被使用的数字且满足整除约束”。因为要求统计的是所有合法排列的数量不需要输出具体排列所以递归函数返回值更适合用“计数”而不是收集路径。状态定义有两个关键变量当前要放置的位置pos以及哪些数字已经被使用。pos从1开始逐个递增每层选择一个合法数字放到pos。终止条件是pos等于n1说明n个位置都填完了计数加1。这道题的暴力解法如果不做优化在n稍微大一点时就会超时因为排列总数是n!。好在它的约束条件限制了分支数量加上提前构建合法匹配表实际运行会比较快。3.2 实现细节从1到n逐个放数第一版直观写法如下def beautiful_arrangement(n): visited [False] * (n 1) count 0 def dfs(pos): nonlocal count if pos n 1: count 1 return for num in range(1, n 1): if not visited[num] and (num % pos 0 or pos % num 0): visited[num] True dfs(pos 1) visited[num] False dfs(1) return count这里用visited数组标记数字是否使用过。注意pos从1开始如果用visited[0]就会造成数组索引和数字错位所以visited长度是n1下标0直接废弃。这是一个非常常见的边界坑小数据可能测不出来但n较大时容易在循环里多访问一位。递归终止前不需要检查pos对应的数字是否合法因为合法条件已经写在了进入递归前的if判断里。有同学会把条件又复制一遍放在终止判断前纯属多余。这个版本在n为15时最坏情况可能仍然很慢。虽然有些分支被整除条件挡掉了但最坏情况下如果某个位置的整除条件对大部分数字都成立比如pos1对所有数字都成立因为1能被任何数整除第一层就有n个分支性能就会迅速变差。3.3 一个容易被忽略的优化预计算合法匹配表优化方法是把“每个位置可以放哪些数字”提前算好。这样在搜索时不需要每次都计算num % pos 0 or pos % num 0直接从预计算的列表里取候选省掉的取模运算在n较大时非常可观。def beautiful_arrangement_optimized(n): matches [[] for _ in range(n 1)] for pos in range(1, n 1): for num in range(1, n 1): if num % pos 0 or pos % num 0: matches[pos].append(num) visited [False] * (n 1) count 0 def dfs(pos): nonlocal count if pos n 1: count 1 return for num in matches[pos]: if not visited[num]: visited[num] True dfs(pos 1) visited[num] False dfs(1) return count这个优化在n不超过15时直观上可能感觉不到太大差别但数据规模一旦上到20左右每个位置候选数量的差异会被放大。更重要的是预计算方式把“合法集合”与“搜索逻辑”分离了代码阅读起来更清晰。我实际测试过n15的输入优化版本比未优化版本快了一倍不止。核心原因不是减少了所有取模运算而是遍历候选列表时通常比遍历1到n全量数字要短等于在循环层面就剪掉了一大堆无效分支。4. 状态机视角当回溯遇上位掩码与状态压缩4.1 为什么需要状态机建模如果只把回溯看作是递归加循环思考很容易停留在“怎么枚举”的层面。可一旦问题规模变大枚举路径会迅速爆炸这时就需要换一个视角把每一层递归看成一个状态把所有可能的决策看成状态转移整个搜索过程就是一个状态机在状态图上走动。这个视角的威力在于它能自然引出记忆化。普通回溯中同一个状态可能被不同的递归路径重复到达。例如在优美排列中已经使用过的数字集合是{1,2}无论先放1后放2还是先放2后放1当前状态在“还需填位置”上是一样的。如果不记忆状态搜索树会重复计算这个子问题。状态机建模要求你明确回答三个问题当前状态怎么表示合法决策是什么状态转移之后如何到达终止状态把这三个问题想清楚代码往往能一次写对。4.2 典型场景集合划分与状态转移状态压缩最常见的形式是用整数的二进制位表示“某个元素是否被使用”。假如n不超过20用一个int就能存下所有集合状态。这类问题很多最典型的是“给定一组数字能否分成若干个和相等的子集”。我以一个简化版为例把一组数字nums分成k个子集每个子集的和相等。回溯时为了不重复处理同一个子集可以维护两个状态当前正在填充的子集和current_sum已经完成多少个完整子集finished。但这还不够需要知道哪些数字已经被使用于是用一个布尔数组或位掩码记录。状态机思路下状态由“已使用数字的掩码”和“当前累计和”共同决定。每次从剩余数字中取一个计算新掩码和新的累计和。这样处理的好处是如果两条路径到达同一个(掩码,累计和)后续结果完全相同就可以缓存。我见过很多同学在该问题上直接暴力回溯代码冗长且超时。如果把问题抽象成状态转移反而更容易写出清晰剪枝。例如当current_sum target时说明一个子集已经填满可以将current_sum重置为0同时继续填下一个子集而不需要回溯重新开始。4.3 状态机回溯的常见板子用位掩码写回溯时我建议遵循以下板子def dfs(state, pos, n): if pos n 1: return 1 count 0 for num in range(1, n 1): bit 1 (num - 1) if state bit: continue if num % pos 0 or pos % num 0: count dfs(state | bit, pos 1, n) return count这是优美排列的位掩码版本。state中第num-1位表示数字num是否已使用。之所以要num-1是因为位移从0开始数字1对应第0位。如果把bit 1 num会多出一位浪费空间且可能越界。该版本配合记忆化就是真正的状态机DFSfrom functools import lru_cache def count_with_memo(n): lru_cache(None) def dfs(state, pos): if pos n 1: return 1 total 0 for num in range(1, n 1): bit 1 (num - 1) if state bit: continue if num % pos 0 or pos % num 0: total dfs(state | bit, pos 1) return total return dfs(0, 1)这里的lru_cache会自动缓存每个(state, pos)的结果。由于state的变化非常多缓存占用内存但通常n小于20时完全能接受。用字典手动实现也可以但Python的lru_cache更简洁不会忘记写返回值。普通回溯和状态机记忆化搜索的差别可以用一个表格概括维度普通回溯状态机记忆化搜索状态表示局部变量或递归参数常压缩为整数/元组重复子问题可能重复计算命中缓存后直接返回适用规模小规模搜索状态数可枚举的中等规模代码结构递归循环递归循环缓存典型应用组合、排列、棋盘集合划分、覆盖、路径状态5. 实操中常见的坑与排查实录5.1 重复组合的根源写组合类问题时最常见的报错是输出结果中出现重复组合。根源通常是递归中每一层的起始索引设置不对。如果你在某层选了第i个元素下一层又从0开始遍历那么[1,2]和[2,1]都会被当成都合法组合输出因为它们只是顺序不同。排查方式很简单打印每一个递归分支的索引观察是否有索引回退的情况。也可以在小数据上手动走一遍比如数组长度为3把所有path输出打印出来看重复出现的位置。修复方式就是固定起始索引如果允许重复取传i如果不允许重复取传i1。5.2 回溯函数的参数设计陷阱参数设计是回溯里最容易埋雷的地方。一个常见错误是把path作为默认参数写在函数定义里比如def dfs(path[]):然后不停append。Python的函数默认参数在定义时只会创建一次多次调用同一个递归函数会共享同一个列表导致结果互相污染。正确做法是每次调用都传入一个新的列表或者在函数内部用局部变量复制。另一个常见坑是修改外部变量时忘记声明。在Python嵌套函数里如果想修改外层函数中的count或ans变量需要加nonlocal如果只修改可变对象的元素比如visited[i] True不需要加因为这是赋值给元素而不是给变量重新绑定。这个区别我在开发时遇到无数次每次都要提醒自己先分清是“修改元素”还是“重新赋值”。5.3 状态机写法中的整数溢出与位运算优先级用位掩码时最经典的坑是运算符优先级。看这行if state bit 0:Python里的优先级高于所以它实际被解析成state (bit 0)结果跟你想要的完全不一样。必须写成if (state bit) 0:这个问题除非编译器报错否则很难发现。建议所有位运算混合逻辑判断时一律加括号哪怕看起来很冗余。整数溢出在Python中不用太担心因为Python的整数可以无限大。如果你用C或Java记得int类型在状态掩码位数超过31时可能溢出这时需要用long或改用布尔数组。状态机题目的数据范围经常n20int在Java里是32位能覆盖C里也基本够用。5.4 剪枝条件与递归深度的配合很多剪枝条件不能瞎加必须和递归深度的语义匹配。比如在集合划分问题中如果当前累计和为0并且尝试某个数字后无法继续可以直接返回False。这个剪枝看起来很玄但实际上是在说当前这个空桶的第一个元素选错了不会再存在可行的方案。这种剪枝只有在递归语义是“按桶顺序填充”时才成立如果换了搜索顺序就不一定安全。调试剪枝时我建议先在小数据上验证不剪枝的版本是正确的再逐步加上剪枝条件每加一个都跑一遍测试数据。一上来就写满所有剪枝一旦出错很难定位是搜索逻辑的问题还是剪枝逻辑的问题。6. 本次综合大练兵的经验沉淀6.1 从“背书模板”到“按需剪枝”很多同学背会了回溯模板但遇到新题还是不会写。原因在于模板只解决“递归框架”的问题没有解决“剪枝策略”的问题。组合总和教给你“同一层跳过重复下一层保持递增”优美排列教给你“预处理合法候选”状态机教给你“用位掩码压缩状态用缓存消除重复子问题”。三个技巧对应三种套路组合起来才是完整的回溯能力。我个人的体会是刷题时不要只追求AC而是每道题都追问一句“剪枝为什么成立”。比如组合总和的排序去重前提是数组有序且相同数字相邻否则candidates[i] candidates[i-1]根本不可靠。只有把这个前提想清楚才能在某天遇到无序输入时知道要先排序。6.2 调试回溯的几个土办法最后分享几个我常用的调试技巧。第一在递归函数开头打印当前层数和状态用缩进展示搜索树能非常直观地看到分支走向。第二把递归深度限制调大一点否则某些合法深搜会因为递归栈溢出而失败Python默认递归深度约1000排列类问题n一大会报错可以临时用sys.setrecursionlimit调整。第三碰到超时先别急着优化剪枝先用小数据集跑一遍确认答案是错的还是慢的。错的话先修逻辑慢的话再剪枝。状态机版本的调试比普通回溯更抽象因为二进制掩码不太好直接看。我习惯写一个小的格式化函数把掩码转换成“哪些数字已使用”的列表打印效果会清楚很多。等程序稳定后这个函数再删掉不影响主逻辑。这套组合题练完我已经明显感到自己搜索类问题的手感好了很多。你如果也想突破回溯的瓶颈建议把三个代码都手敲一遍再跑几组边角数据。特别是优美排列的位掩码记忆化版本值得反复对比普通回溯的运行时间体会状态机带来的不同。