回溯算法我用了快十年从最早在学校里写 N 皇后、迷宫求解到后来工作里拿它做调度排班、权限组合校验、甚至电商优惠券叠加计算可以说这套“穷举撤销”的思路是解决一大堆看似无解问题的底牌。很多初学者一看到“回溯”两个字就发怵觉得是不是又要背什么高深理论了。其实把它的本质拆开就是一件事暴力遍历所有可能但在遍历过程中一旦发现当前路径已经没戏了立刻止损回头换一条路继续试。这篇文章我想把经典的回溯算法完整拆一遍不讲废话直接说你最该掌握的核心框架、三个必练的经典题目全排列、组合、子集这种以及我在实际开发里头踩过的坑和总结出来的剪枝技巧。不管你是刚接触算法的新手还是准备面试的求职者或者工作中需要做一些组合枚举类的需求这篇都适合你当作一份能直接“抄作业”的参考。1. 回溯算法的核心思想本质是一次“带后悔药的深度优先遍历”很多人上来就背什么“回溯递归剪枝”这个说法没错但太干瘪不利于真正理解。我用一个更直白的说法来解释回溯其实就是把问题想象成一棵树树的每个节点代表“当前已经做出的选择”根节点是“还没有做任何选择”叶子节点是“全部选择都做完了”。你要做的就是从根出发沿着分支把整棵树走完每走通一条路就得到一组可行解。1.1 为什么它和普通的暴力枚举不一样普通的暴力枚举比如嵌套几层 for 循环去凑组合数一旦问题的规模变大循环层数就没法固定了。比如要从 10 个数里选 4 个你可以写四层循环但如果是选 20 个呢循环层数就得动态变化代码根本没法写。回溯算法就解决了这个问题——它用递归代替了固定层数的循环递归的深度就是“你还需要做多少个选择”。所以它天然适合处理这类问题排列类给定一组数输出所有排列方式组合类给定一组数选出满足条件的所有组合子集类给定一组数输出所有子集棋盘搜索类N 皇后、数独、单词搜索约束满足类括号生成、图着色、任务调度。它不依赖循环层数固定而是靠递归状态重置把一个原本需要“物理上写 N 层循环”的问题转化成“逻辑上走一棵树”的问题。这一点是回溯最核心的思维转变。1.2 用生活例子快速建立直觉你可以把回溯想象成走迷宫。你手里拿着一团线从入口出发每到一个岔路口选一条路走进去同时放线。如果走到死胡同你就顺着线退回到上一个岔路口换另一条路继续试。这里的“线”就是递归的调用栈退回去重新选路就是“撤销选择”。另一个例子是解数独。你在某个空格填了一个数字然后继续往下填填到后面发现行不通说明前面那个数字填错了你就把它擦掉换一个数字重新填。这个“擦掉重填”的动作就是回溯里的“撤销选择”。这些例子看着简单但已经把回溯的全部核心要素都包含了路径你已经填过的数字、走过的岔路、选择列表当前空格还能填哪些数、当前路口有哪几条没走过的路、结束条件全部填完、走到出口。1.3 回溯算法的三个关键要素当你拿到一道需要用回溯解决的题先不要急着写代码先在纸上回答三个问题路径你已经选了哪些元素怎么把这些选择记录下来选择列表当前这一步还有哪些元素可以选哪些已经被选过了、需要排除结束条件什么时候说明一条完整路径走完了什么时候需要立刻终止递归这三个问题想清楚代码结构基本上就出来了。路径用组合结果记录下来递归结束时加入答案集选择列表用循环遍历候选集合并排除非法选项结束条件写在递归函数的开头。2. 回溯算法的万能框架一套模板吃透所有题型我在指导新人刷题时反复强调一个观点**先把框架背熟再谈变通。**回溯算法的代码结构极其稳定九成以上的题都是在下面这个框架上加加减减。2.1 核心代码模板Python 为例def backtrack(路径, 选择列表): # 结束条件路径已经完整把当前结果加入答案 if 满足结束条件: result.append(路径[:]) # 注意一定要拷贝不是直接 append return # 遍历当前选择列表 for 选择 in 选择列表: # 做选择把当前选择加入路径 路径.append(选择) # 递归进入下一层决策树 backtrack(路径, 新的选择列表) # 撤销选择回溯的关键一步 路径.pop()这段代码是回溯的“骨架”。理解它的核心其实就三句话**进入递归前修改状态递归返回后恢复状态。**很多新人写错回溯不是不知道这个模板而是在细节上出了问题。2.2 模板中隐藏的细节为什么 append 的是路径副本这是一个非常容易被忽略、却又极其关键的细节。如果你在代码里写result.append(path)而不是result.append(path[:])那你会得到一个非常诡异的 bug最后 result 里的所有结果都一样而且都是空的。原因很简单path是一个列表对象它在递归过程中不断被修改。result.append(path)存的是列表对象的引用而不是存了一份快照。当递归结束、所有path.pop()执行完毕path最终变成空列表而 result 里面存的所有“引用”指向的都是同一个空列表。我第一次被这个问题坑的时候花了半个小时才反应过来。所以这里强调一下收集结果时必须拷贝一份当前路径的副本。2.3 模板演变的常见方向基础模板背熟后你会发现在不同题目里模板会发生几个方向的演变带 for 循环起始位置的模板组合问题里每次递归从start1开始避免重复选取之前已经走过的元素这种叫“按位置推进”带 used 数组的模板排列问题里因为元素的顺序是有意义的每层循环都需要从头开始但要跳过已经用过的元素带剪枝条件的模板先对候选集排序然后判断当前元素与前一个元素相同且前一个没用过就跳过这种用于结果去重提前终止条件的模板比如组合总和里如果当前累加值已经超过目标直接 return不再往下深入。这些演变看起来五花八门但本质上都是在回答我之前说的那三个问题路径怎么记录、选择列表怎么约束、结束条件怎么判定。框架的骨架没有变。3. 经典题目实战拆解三个题目建立完整手感光背模板没用必须拿具体题目练。我选了三个最经典、最能体现回溯不同侧面的题目分别对应的应用场景是排列、组合、棋盘搜索。这三个题吃透基本你就摸清回溯的路数了。3.1 全排列最标准的“选一个就标记一个”题目描述很简单给定一个不含重复数字的数组nums返回所有可能的全排列。比如输入[1,2,3]输出 6 个排列。为什么排列问题需要用 used 数组因为排列讲究顺序[1,2,3]和[2,1,3]是两个不同的结果。每一层递归都可以从 nums 的所有元素里选但你不能重复选同一个元素。这时候就需要一个used数组来标记哪些元素已经在当前路径里了。def permute(nums): result [] used [False] * len(nums) def backtrack(path): # 结束条件所有元素都选完了 if len(path) len(nums): result.append(path[:]) return # 每一层都从头遍历所有元素 for i in range(len(nums)): # 排除已经选过的元素 if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归 backtrack(path) # 撤销选择 path.pop() used[i] False backtrack([]) return result这个题的要点有两个。第一个是used数组和path的联动——进递归前标记出递归后立即恢复这个一前一后的对称性必须保证。第二个是结束条件是len(path) len(nums)代表路径里的元素个数已经和原数组一样长。我见过不少同学写的全排列没有used数组而是直接在nums里把用掉的元素删除这样也能做但删除列表元素的代价是 O(n)效率不如 used 数组 O(1) 搞定。而且用del或remove修改原数组稍不注意就会导致索引错乱。所以标准解法还是用标记数组。3.2 组合总和剪枝和排序的第一次正面交锋“组合总和”是一个比全排列更有实用价值的题。给定一个无重复元素的数组candidates和一个目标数target找出所有可以让数字之和等于 target 的组合。candidates中的数字可以无限制重复使用。这个题我强烈建议每个人手动跑一遍因为它逼你理解剪枝的本质。def combination_sum(candidates, target): result [] candidates.sort() # 排序是剪枝的前提 def backtrack(start, path, total): # 结束条件和已经达到 target if total target: result.append(path[:]) return # 遍历可选元素从 start 开始避免重复组合 for i in range(start, len(candidates)): # 剪枝如果当前元素加上去已经超过 target # 由于数组已排序后面的元素只会更大直接 break if total candidates[i] target: break # 做选择 path.append(candidates[i]) # 递归注意 start 从 i 开始因为元素可以重复使用 backtrack(i, path, total candidates[i]) # 撤销选择 path.pop() backtrack(0, [], 0) return result这个题的关键点在于start参数的传递。因为题目允许同一个元素重复使用所以递归时start仍然传i而不是i1。如果你改成i1那就变成“每个元素只能用一次”的组合问题了。这个差别是这一类题最容易出错的地方。再来说剪枝。很多初学者不理解为什么排序之后可以break。我解释一下candidates排序后是递增的如果当前的candidates[i]加上去都已经超过 target 了那后面的元素只会更大更不可能满足要求所以不需要再遍历后面的元素了。这种情况下用break而不是continue是因为后面已经没有任何可能直接退出整个循环。这个剪枝能把大量的无效递归提前拦住性能提升是数量级的。3.3 N 皇后经典棋盘搜索剪枝的集大成者N 皇后的问题是在一个 N×N 的棋盘上放置 N 个皇后使得它们互不攻击。皇后可以攻击同一行、同一列、同一条对角线上的其他棋子。这个问题比前两个复杂因为它不仅要求你“选元素”还要在每一步验证当前放置是否合法。我用一个简单的方案来实现合法性检查cols集合记录已占用的列diag1记录“行列”的差对应从左上到右下方向的斜线diag2记录“行-列”的差对应从右上到左下方向的斜线。def solve_n_queens(n): result [] cols set() diag1 set() diag2 set() def backtrack(row, board): # 结束条件所有行都放完了 if row n: result.append([.join(r) for r in board]) return # 第 row 行逐列尝试放置皇后 for col in range(n): d1 row - col d2 row col # 剪枝列冲突 或 对角线冲突 if col in cols or d1 in diag1 or d2 in diag2: continue # 做选择 cols.add(col) diag1.add(d1) diag2.add(d2) board[row][col] Q # 递归到下一行 backtrack(row 1, board) # 撤销选择 cols.remove(col) diag1.remove(d1) diag2.remove(d2) board[row][col] . board [[. for _ in range(n)] for _ in range(n)] backtrack(0, board) return result这个题的难点在于对角线的判断。为什么row - col相同就说明它们在一条左上到右下的斜线上你可以自己画一个 4×4 的棋盘把每个格子的row - col值标出来你会发现从左上到右下的斜线上所有格子的row - col都相等。同理row col相等代表在另一条对角线方向上。用集合来判断冲突复杂度 O(1)非常高效。N 皇后是一个很考验“做选择撤销选择”同步性的题目因为你在递归前修改了三个集合和一个棋盘数组递归后每一个都要恢复。漏掉任何一处下一轮递归的结果就会出错。这也是实际开发中回溯代码“看起来对跑起来错”的最常见原因。4. 剪枝与去重回溯真正的分水岭很多新人的回溯代码跑一些小规模数据是没问题的但一旦数据量上来立刻卡死。这不是回溯算法本身的问题而是你没做剪枝。剪枝是回溯算法里最值得花时间研究的环节它决定了你的算法是“能跑”还是“能高效地跑”。4.1 剪枝的两个主要方向剪枝可以分为两大类可行性剪枝和重复性剪枝。可行性剪枝是说在递归走进去之前先用条件判断当前这条路还有没有可能走到终点。比如组合总和里一旦当前和已经超过 target直接 breakN 皇后里如果当前位置和已放置的皇后冲突直接 continue。这些判断能提前终止大量无效分支。重复性剪枝是说当候选集合里有重复元素时需要通过合适的策略避免生成重复结果。比如给定[1,1,2]求不重复的排列如果你不处理会出现两个[1,1,2]。这时候的处理方式通常是先将候选数组排序让重复元素相邻然后在递归循环中判断当前元素是否和前一个元素相同且前一个元素还没有被使用过如果是就直接跳过。4.2 排序used 数组组合去重的标准操作我以“组合总和 II”不允许重复使用同一元素但候选数组可能有重复为例来说明去重逻辑。def combination_sum2(candidates, target): result [] candidates.sort() def backtrack(start, path, total): if total target: result.append(path[:]) return for i in range(start, len(candidates)): # 此次循环中如果当前元素和前一个相同说明已经处理过 # 跳过避免生成重复组合 if i start and candidates[i] candidates[i - 1]: continue if total candidates[i] target: break path.append(candidates[i]) backtrack(i 1, path, total candidates[i]) path.pop() backtrack(0, [], 0) return result这里关键的一行是if i start and candidates[i] candidates[i - 1]。为什么是i start而不是i 0因为start表示本次循环的起点。当i等于start时即使它和前一个元素相同那也是同一层循环的第一次合法选择不能跳过只有当i大于start时才说明当前元素在该层已经被处理过了通过前一个相同元素。这个细节非常容易被写错。我见过很多人把条件写成if i 0 and candidates[i] candidates[i-1]结果发现正确答案被跳掉了一大半。原因就是没有理解start在该层的语义。4.3 剪枝对性能的影响到底有多大我给你一组具体数据感受一下。求从 1 到 40 中选出所有和为 80 的组合候选集合大小是 40。不做任何剪枝直接穷举需要检查的组合数量约是 C(40, k) 的总和量级在千亿甚至更高程序基本跑不完做“和超过 target 就终止”的剪枝因为元素是正数一旦超过 80 就不会再往下递归实际运行的递归次数会显著下降到百万级再配合排序和“跳过重复起点”的剪枝进一步过滤掉大量对称重复的分支实际耗时可以从“无法完成”降到几十毫秒。所以剪枝不是锦上添花而是很多回溯题目能通过的必要条件。凡是遇到数据范围超过 20 的题目你都要问自己一句剪枝做够了吗5. 回溯算法的实战应用不止是面试题很多同学学完回溯觉得它只是用来刷题应付面试的工作里用不到。这个想法我不同意。我在实际项目里用到回溯的场景至少有这么几类电商优惠满减的组合推荐给定用户手中的几张优惠券找出所有能和订单金额匹配的叠加方案权限系统的角色组合校验用户拥有多个角色每个角色有一组权限位求用户是否拥有指定的全部权限以及所有满足条件的角色组合排班调度问题把一批人员分配到不同时段的班次满足每人每周不超过规定工作时长、每个班次至少有多少人覆盖测试用例生成给定一堆参数的可选值自动生成全组合、全排列形式的测试用例资源分配与路径规划比如在有限的仓库容量约束下找出所有可以配齐订单的拣货方案。这些场景有一个共同特点候选集合不大通常十几个到几十个但组合爆炸起来非常可怕。用回溯剪枝恰恰能在“可接受的枚举规模”内找到全部可行解。如果你把这些场景换成数学建模里的整数规划当然也能做但往往杀鸡用牛刀而且调整约束条件很麻烦。回溯代码短、逻辑直白、改起来快这种灵活性和可维护性在实际业务里非常重要。我之前做一个优惠券叠加计算的模块时看到同事用的是多层嵌套循环硬编码了三张券的组合。后来业务方说“用户可能同时拥有五张券我需要算所有可能的叠加”那个硬编码方案直接废掉。我替换成回溯算法核心代码不到三十行把“券数量”变成了一个传参业务扩展变得极其简单。这个经历让我确信回溯是工程里一个实用的“软性武器”值得熟练掌握。6. 常见问题与排查技巧实录这部分是我最想分享的。回溯代码看着简单但写对不容易。下面这几个问题几乎每个初学者都会遇到我也都踩过。6.1 结果全部相同或者为空检查你的 append 拷贝这是最经典的问题。如果你在收集结果的地方写的是result.append(path)那么所有结果都会指向同一个 path 对象最终因为递归结束后的统一 pop全部变成空列表。解决办法是写result.append(path[:])把 path 的副本存进去。类似的场景还出现在其他语言里。Java 里要写new ArrayList(path)C 里要写result.push_back(path)但它默认也是拷贝所以反而不容易踩坑。Go 里要注意切片底层共享数组的问题也需要拷贝后再加入结果集。总之一句话存快照不存引用。6.2 递归深度太深导致栈溢出回溯本质是深度优先遍历递归深度等于你选择的层数。如果数据规模很大比如求长度为 30 的全排列递归深度就是 30这在大多数编程语言里还不会爆栈。但如果数据量到几千递归深度跟着到几千Python 默认递归限制是 1000 层就可能抛 RecursionError。遇到这种问题手段有几个用sys.setrecursionlimit()调高递归限制但这不是根本解决办法优先考虑剪枝把不必要的递归深度提前砍掉如果必须处理超大候选集考虑用显式栈把递归改成迭代虽然代码丑一点但不会爆栈。实际工程里我很少遇到必须处理几千层递归的场景因为回溯本身面向的就是“候选集不会太大”的问题。真到了那个规模算法层面可能就该换方案了。6.3 结果重复先排序再做同层去重如果你发现输出了重复的组合或排列基本可以确定是重复性剪枝没做。解决方案我上面已经讲过候选集排序然后加上if i start and candidates[i] candidates[i-1]: continue这类判断。这里再补充一个容易混淆的细节。排列问题的去重和组合问题的去重判断条件写法不同。排列去重需要依赖 used 数组逻辑类似if i 0 and nums[i] nums[i-1] and not used[i-1]: continue。这个条件的意思是当前这个元素和前一个相同而前一个没有被用过说明当前分支会生成和前一个相同的排列需要跳过。为什么必须是not used[i-1]而不是used[i-1]因为当used[i-1]为 True 时说明前一个元素已经被用在了当前路径的前面位置这时候当前元素作为后续位置选入是合理的只有当used[i-1]为 False意味着我们正在同一层尝试和前面相同的元素那就会产生重复。这个判断很绕但理解了之后你会觉得它非常合理。6.4 做了选择忘了撤销状态泄漏“做选择和撤销选择没有对称”是回溯代码里最隐蔽的 bug。比如你在递归前改了 used 数组和 path但递归后少写了一行path.pop()或者used[i] False那么上一层递归会带着这一层修改过的状态继续跑产生一堆错误结果。排查这种问题有个好方法把递归函数想象成一个“严格对称的括号”。括号内是递归调用括号外左边写“选择”右边写“撤销选择”两边必须一一对应。每当你对某个数据结构做了修改就问自己递归返回后有没有恢复原状。画递归调用栈的草图也能帮你定位问题尤其是 N 皇后这种同时修改了多个状态的题。6.5 找到第一个解就停不下来加个全局终止标志有些题目不需要找到所有解而只需要一个可行解比如单词搜索、解数独。这时候如果你还用“收集所有解”的思路写会白跑很多分支。解决办法是在递归函数返回 bool 值找到解后直接返回 True同时层层向上传播终止后续搜索。def backtrack(...): if 找到解: return True for ...: if backtrack(...): return True return False这种写法能把“全量枚举”变成“短路枚举”在只求一个解的场景下效率提升非常大。7. 学习路径建议从入门到熟练的三个阶段最后我给想系统掌握回溯算法的同学一条学习路径按顺序推进你会感觉到明显的进步曲线。第一阶段模板模仿期。把上面全排列和组合总和的代码亲手敲一遍不要复制粘贴。敲的过程中会自然记住框架结构也更容易发现自己在哪个环节会遗漏状态恢复。跑通之后尝试把“结束条件”改掉比如排列改成子集理解它们之间的差异。第二阶段题型分类期。把常见回溯题型按“排列、组合、子集、分割、棋盘”五类分好每类做两三道题。重点练习各种题型的剪枝条件是怎么写出来的。做这个阶段的时候不要追求题量要追求“能不能看着题目说出解法思路”。第三阶段优化内化期。尝试自己给一道题设计剪枝策略并且用大一点的数据测试比较不同剪枝写法的耗时差异。到了这个阶段回溯在你的思维里就不再是一个需要背的模板而是一套可以灵活运用的方法论了。我自己现在遇到组合类问题时第一反应不是去套模板而是先想清楚三件事状态是什么、状态怎么变化、怎么从变化中回退。想清楚这三件事代码自然就写出来了。这个思考方式才是回溯带给我最大的收获。