“找出所有满足条件的组合……”这类问题日常开发里你可能已经撞上过很多次比如扑克牌凑点数、订单凑满减、路径规划的所有可行选项。很多人第一反应是叠几层 for 循环可循环层数一旦跟着输入规模走代码立马就编不出来了。这时候递归配合穷举搜索是最直接、最朴素也最不容易出错的解法。本篇文章我打算从递归的底层思维讲起拿几个我实际写过的经典案例组合求和、全排列、N 皇后这类一步步拆给你看把“选择-递归-撤销”这套模板讲透再聊聊剪枝、去重、栈溢出这些实战绕不开的坑。无论你是刚开始刷题的新手还是在业务里跟搜索/推荐/调度逻辑打交道的开发者这篇文章都能给你一套拿来就能用的思路参考。1. 先搞清楚递归和穷举搜索到底解决什么问题1.1 穷举搜索的“穷”字才是核心穷举搜索说白了就是把所有可能的情况都拉出来过一遍筛子一个都不放过。它跟数学里的“枚举法”是一回事但放到代码里难点从来不是“要不要穷举”而是“怎么穷举才能不重不漏”。举个最简单的例子一个班有 5 个同学老师要从里面挑 3 个人参加比赛问有几种挑法。你手动列的话可能会先固定第一个人再在剩下的人里选两个这个过程本质上就是在构建一棵“选择树”。每一层代表“当前位置选谁”走到底就得到一种完整方案。穷举搜索之所以难是因为当候选人数变成 20选 10 个的时候这棵树的分支数量会膨胀到让人头皮发麻——这就是所谓的“组合爆炸”。所以穷举搜索的真正关键不是“把所有可能性在脑子里想清楚”而是“让计算机按照一个固定的、有规律的流程自己长出一棵搜索树来”。而这个流程用递归来表达是最顺手的。1.2 递归为什么是穷举搜索的天然载体递归的思维起点其实非常朴素一个大问题如果能拆成“一个小问题 一个规模更小的同类问题”那就可以用同一个函数反复处理。你看热搜词里的“递归将一个整数 n 转换成字符串”就是个特别直观的例子def int_to_str(n): if n 10: return chr(ord(0) n) return int_to_str(n // 10) chr(ord(0) n % 10)这段代码没有任何循环它每次把 n 除以 10 得到一个更小的数继续用同样的规则转换最后再拼上当前这一位。递归在这里干的事情就是把“转换整数”这个大任务切成了“转换更小的整数 处理个位数字”这样的小任务一层层递下去再一层层归回来。穷举搜索也是一样的逻辑。你站在搜索树的某个节点上需要做的决定是“接下来选哪个元素”每选一个元素就进入一个规模更小的问题剩余可选项变少剩余目标值变小。这个“继续选”的动作和父节点上“开始选”的动作逻辑完全一致所以用同一个递归函数就能描述整棵树。这就是我说的“递归是穷举的天然载体”——它天然地帮你维护了搜索进度。1.3 递归穷举的通用模板选择、递归、撤销我刷了这么多年算法题参与过的项目里也写过不少暴力搜索逻辑最后总结下来所有递归穷举都可以套用一个三部曲模板选择在当前状态下枚举所有可能的分支选项。递归把状态更新后交给下一次递归调用进入下一层。撤销递归返回后把状态恢复到选择之前方便尝试下一个分支。这个“撤销”步骤往往是新手最容易漏掉的。你想想如果走到一个分支后发现此路不通返回上一层想试别的路可路径上还留着上一个分支留下的“痕迹”那后面的结果必然全乱。所以“回溯”这个词强调的正是这个“撤销”动作——递归穷举和回溯算法在代码形态上基本是一回事区别只是回溯更强调这个回退过程。有了这个模板后面的案例就好办了。你不需要每次从零开始思考穷举结构而是先套模板再针对具体问题加条件判断和剪枝逻辑。2. 核心案例拆解组合求和问题的完整实现2.1 先看一个我会在面试里反复出的问题给定一个无重复元素的数组candidates和一个目标数target找出所有可以使数字和为target的组合。同一个数字可以重复使用组合之间不能重复。比如输入candidates [2, 3, 6, 7]target 7输出[[7], [2, 2, 3]]这个题非常经典因为它同时考察了你对递归、穷举、状态回溯、剪枝四个点是否理解到位。我第一次刷到这题时第一反应是“这得多少个嵌套循环啊”——这就是没吃透递归穷举模板时会产生的典型焦虑。2.2 手工穷举到递归穷举的思维转换先别急着写代码。我来模拟一下手工穷举这个过程。target 是 7可选的数字是 2、3、6、7。假如我要手动列所有组合我会这样做先选一个数字比如选 2那么问题变成“从 [2, 3, 6, 7] 里选数字凑出 5”在凑 5 的问题里我可能再选一个 2问题又变成“凑 3”……一直凑到 0说明这条路走通了凑成负数说明这条路走死了。这个过程里有一个细节需要注意为了避免组合重复我给自己定了一条规则——“只能选当前位置及之后的数字”。也就是说第一轮选了 2后续只能在 2、3、6、7 里选第一轮选了 3后续只能在 3、6、7 里选。这样就不会出现 [2,3] 和 [3,2] 这种重复组合。这个“不回头看”的去重策略是穷举搜索里最重要的规则之一后面我会拿它单独讲。把这个手工流程改写成递归其实就是三步当前函数负责解决“从索引 start 开始凑出剩余值 remain”这个子问题。在循环里枚举 start 到末尾的每个候选数字把它放进路径中。调用递归解决“更新后的剩余值”问题调用完再把该数字从路径中移除。2.3 组合求和的代码实现与参数设计下面这段是我在实际练习里最终沉淀下来的版本语言用 Python注释写得比较细def combination_sum(candidates, target): result [] # 存所有合法组合 path [] # 记录当前路径也就是正在构建的组合 # 先排序。排序不是必须的但对剪枝帮助很大原因见下文 candidates.sort() def dfs(start, remain): # 找到一个合法组合剩余值恰好被凑满 if remain 0: result.append(path[:]) # 注意这里必须拷贝 path否则后续改动会影响已存入的结果 return # 遍历可选数字从 start 开始保证组合不重复 for i in range(start, len(candidates)): cand candidates[i] # 剪枝如果当前数字已经大于剩余值后面更大的数字更没有希望 # 由于数组已排序直接终止本层循环 if cand remain: break # 选择当前数字 path.append(cand) # 递归。这里仍传 i 而不是 i1因为同一个数字允许重复使用 dfs(i, remain - cand) # 撤销选择回到上一层状态 path.pop() dfs(0, target) return result几个容易出问题的地方我挨个说明。首先是path[:]这一手。Python 里result.append(path)存的是path这个对象的引用后面一旦执行path.pop()已经存进result里的路径也会跟着变。我第一次写的时候在这里踩了大坑排了半天错才发现是浅拷贝的问题。其他语言也是一样的道理存列表或数组时该 clone 就要 clone。其次是递归参数传i还是i1。题目允许同一个数字重复使用所以选了当前数字后下一层仍然可以从当前位置开始再选它如果题目改成“每个数字只能用一次”这里就要改成i1。这个细微差别是很多变体题的考点。再有就是剪枝。为什么排序后能用break因为数组从小到大排列后一旦发现某个cand已经大于remain说明它后面的数字都大于等于它必然也大于remain同一层循环再往后走全是无效分支可以直接结束整个循环。如果不排序就只能用continue跳过当前这个数字效率会差一些。别看这点差别不大在 candidates 长度很大的时候排序剪枝能省下指数级的时间。2.4 跑一遍代码看清楚搜索树长什么样还是用 candidates [2, 3, 6, 7]target 7 来跑第一层start 0remain 7循环遍历 2、3、6、7选 2path [2]递归去凑 5第二层选 2path [2,2]递归去凑 3第三层再选 2凑 12 1break第三层选 3凑 0记录 [2,2,3]第二层选 3path [2,3]递归去凑 2第三层选 2凑 0记录 [2,3,2]不对注意我们的 start 规则第二层选 3 时i 指向 3 的下标 1第三层从下标 1 开始也就是只能选 3、6、72 已经够不到了所以不会产生 [2,3,2]选 3path [3]递归去凑 4后续只会产生 [3,3]4-31无解等等选 6path [6]残留 16 1break选 7path [7]凑 0记录 [7]最终得到 [[2,2,3], [7]]结果正确。你注意看第二层选 3 的情况因为我们的 start 规则递归过程会自动跳过下标在 start 之前的元素。这意味着 [2,3] 和 [3,2] 这种顺序不同的排列只会出现一次天然去重。这一招可比最后用 set 去重高效得多也优雅得多。3. 递归穷举的复杂度分析与优化方向3.1 先会估算解空间才知道程序会不会跑死写递归穷举之前一定要先估算一下解空间的上界。否则写出来一个函数在测试用例上跑得飞快一上真实数据就卡死那就不叫解决问题叫制造事故。解空间的估算取决于你的问题类型子集枚举类比如组合求和每个元素有选或不选两种状态理论上界是 2 的 n 次方。排列类比如全排列n 个元素的全排列数量是 n 的阶乘。组合类从 n 个里选 k 个数量是 C(n, k)即 n! / (k! * (n-k)!)。棋盘类比如 N 皇后最粗暴的上界是 n^n每行有 n 个列选择加上约束剪枝后实际会远小于这个值。拿组合求和来算笔账如果 candidates 有 20 个元素target 又比较大导致每个元素都可能被重复选那么搜索树的深度就可能达到 target 除以最小元素的值分支因子是 20理论节点数会非常爆炸。这也是为什么这种题在面试里通常会限制数组长度不是没有道理的。学会估算解空间最大的作用是帮你建立“这个方案到底能不能跑”的直觉。我见过不少初学者拿到问题就套递归结果输入一放大就变成“指数级灾难”不是思路错了而是没有提前评估这个问题的规模到底允不允许你用穷举。3.2 剪枝省掉那些明知道没希望的分支穷举搜索最容易被人诟病的就是“慢”但慢不慢很大程度取决于你有没有剪枝。剪枝本质上就是“根据当前信息提前预判这个分支不可能产生合法解直接跳过”。常见的剪枝策略有这么几类可行性剪枝当前路径已经不可能走到合法结果了直接返回。比如组合求和里cand remain就直接 break零钱兑换里剩余金额减成负数就返回。最优性剪枝当前路径的成本已经超过已知最优解了直接放弃。这个多用于最优化问题比如旅行商问题里的分支限界。约束传播剪枝提前判断当前位置是否还能放元素。比如 N 皇后里当前行要放的列和对角线已经冲突就跳过。剪枝写得好不好直接决定了同一个算法在不同人手里的性能差距。我见过同样是解数独有人要跑几十秒有人毫秒级出结果差别就在于剪枝策略和变量的选择顺序——先填约束最多的格子能大幅减少无效分支。这就是所谓的“剪枝顺序优化”。但我也得提醒一句剪枝逻辑别写得太激进。剪枝的目的是排除“必然无解”的分支而不是排除“看起来可能无解”的分支。如果你对题目的约束理解不透彻为了性能硬加剪枝条件很容易把合法解也一起剪掉。这种 bug 最难排查因为结果不是报错而是“少了一个答案”。3.3 回溯不是递归的子集它们是两件相关的事很多人把回溯backtracking和递归混为一谈。严格来说回溯是一种算法思想递归是一种编程手段。回溯算法必然是递归实现的但递归不只是用来做回溯。组合求和、全排列、N 皇后这类问题用的都是回溯我们一边深度优先地构建解一边在走错路的时候回到上一个岔路口换个选择继续走。回溯里那个“回”字对应的就是代码里的“撤销选择”操作。而像二分查找、归并排序这类递归用法递归返回的时候是在“收集结果”或“合并结果”并没有反复试错的过程所以它们不算回溯。你看热搜词里的“递归二路归并排序”就是把数组一分为二、各自排序、再合并递归在这里是“分而治之”的工具而不是穷举搜索的载体。搞清楚这个区别很重要。至少能帮你避免一个常见误区一看递归就想着“这是不是要设一个全局变量存所有解”。其实很多递归函数根本不需要全局解集它的返回值就是最终答案比如归并排序返回有序数组。4. 实战中的常见问题与排查技巧4.1 问题一无限递归程序直接栈溢出递归最让人头疼的运行时错误之一就是无限递归。写递归必须满足两个条件有递归出口base case并且每递归一层问题规模都在缩小。只要其中一个不满足程序就会无限地调用自己直到调用栈超出限制直接崩溃。排查技巧很简单先检查 base case。组合求和里if remain 0是出口但你还得保证remain一定会减小。什么时候不会减小如果你允许候选数字为 0或者参数传递写错导致 remain 根本没变就会出现死循环。还有一种隐蔽情况是函数参数设计不严谨递归调用时把本来该更新的状态传成了旧状态。为了稳一点我倾向于在开发阶段就给递归函数加一个“最大深度保护”比如传入 depth 参数超过某个阈值就抛异常或返回空。这能让你尽早发现问题而不是等到栈溢出才排查。4.2 问题二结果重复穷举变成了“穷折腾”穷举搜索要求“不重不漏”但实际很容易漏了“不重”这一半。重复的来源往往就一个在搜索过程中把相同元素的不同顺序当成了不同组合。最经典的解法就是我在组合求水里用的“start 参数法”每层递归只从当前索引开始往后遍历绝不做“回头看”。这样就能保证同一个组合只按某种固定顺序被枚举出来。如果题目数组本身带有重复元素比如 nums [1, 1, 2] 求全排列你还需要先对数组排序然后在同一层循环里跳过和前一个相同的元素。这里有个很关键的小细节跳过条件是i 0 and nums[i] nums[i-1] and not used[i-1]。为什么还要加not used[i-1]这个条件因为如果是第一次使用这个重复元素前一个还在路径里这个分支是合法的只有当上一个相同元素已经被撤销不再处于 used 状态时才说明当前这个元素是“同一层里的重复尝试”需要跳过。这个逻辑我第一次写的时候就漏了结果在全排列里出现了不少重复排列排查了很久才发现是这里的问题。4.3 问题三数据太大内存与耗时双双失控递归穷举的内存开销来自两块递归调用栈本身以及你用来存结果的全局数组。当解空间特别大的时候就算剪枝剪得很干净合法解本身就多结果集占的内存也会很惊人。这时候有几个实用的手段边搜索边处理不要等全部解都生成完再处理。比如你需要统计满足条件的组合个数那就只维护一个计数器而不是把所有组合都存下来。如果必须输出所有解可以考虑先输出到文件或消息队列分批处理。调整语言层面的递归深度限制。Python 的sys.setrecursionlimit()可以把默认的 1000 层上限调高但调高后仍然可能因真实栈内存不足而崩溃所以要谨慎使用。在耗时的递归函数里尽量少做无谓的数组拷贝和对象创建。比如上面的path[:]拷贝只在确认要记录结果时才做不要在每次递归调用时都拷贝。4.4 快速排查清单一套我自己总结的流程递归穷举的 bug 比较隐蔽下面是建议按顺序执行的排查清单先打印递归函数的入口参数和当前 path看状态转移是否符合预期。检查递归出口是否覆盖了所有终止情况特别注意边界值0、空数组、负数。逐行确认“选择、递归、撤销”三件事都执行了且顺序正确。看是否用了复制而非引用传递尤其是在 Python、Java 里存结果时。拿一个极小规模的输入手动推导一遍搜索树再跟程序输出对比。最后再怀疑剪枝逻辑是不是写过头、把合法分支也砍了。这套流程帮我解决过至少几十次递归相关的疑难杂症。独门建议是把打印放在撤销之前这样你能看到每个分支“进入时的状态”和“离开时的状态”一目了然。5. 递归穷举的变体场景与进阶方向5.1 全排列在路径上做文章组合求和是在“选数字”全排列则是把“顺序”也纳入考虑。给定 nums [1, 2, 3]我们需要输出 [1,2,3]、[1,3,2]、[2,1,3] 等 6 种排列。全排列的递归模板跟组合求和比多了一个 visited 数组来记录哪些元素已经在当前路径上。核心逻辑是def permute(nums): result [] path [] used [False] * len(nums) def dfs(): 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]) dfs() path.pop() used[i] False dfs() return result这里没有 start 参数因为每个元素在任何位置都可能出现但多了一个“已使用”的标记。递归的层数是固定的 n 层每一层都在做“哪个还没用过的元素放到当前位”的穷举。你会发现它依然完美符合“选择-递归-撤销”模板只是把“不能重复使用元素”这个约束放在了 used 数组上。5.2 N 皇后用剪枝解决老牌难题N 皇后问题是递归穷举剪枝的经典组合。你要在 n x n 的棋盘上放 n 个皇后要求任何两个皇后不能在同一行、同一列、同一对角线上。以行号为递归层级每层决定这个皇后放到哪一列。暴力穷举所有摆法然后用剪枝去掉互相攻击的情况。判断两个位置 (r1, c1) 和 (r2, c2) 是否在同一对角线核心规律是|r1 - r2| |c1 - c2|。这个判断写成代码就是检查“行号差是否等于列号差”。N8 时把所有 8 皇后摆法全部穷举一遍8^8 1677 万个组合听起来很吓人可一旦加上剪枝实际搜索量会急剧下降几十毫秒就能跑完。这个案例特别适合用来感受“剪枝”到底能把搜索空间压缩到多小。5.3 从穷举递归到分治递归归并排序与二分树聊了这么多回溯和穷举我想顺便说一句递归这个工具远不止用来穷举。热搜词里有“递归二路归并排序”它就是分治思想的代表。归并排序把数组对半切开递归地排好左右两半再合并起来。这里的递归不是在“试错”而是在“分而治之”而且它的时间复杂度从穷举的指数级直接降到 O(n log n)。为什么同样是用递归效率差距如此之大根本原因在于穷举递归会访问解空间里所有节点而分治递归通过“规模减半”把总工作量限制在了对数线性级别。所以当你遇到一个问题时先别急着套穷举要想清楚这个问题到底需不需要看遍所有可能性有时候只需要“局部最优”或“合并子结果”就够了。“verilog递归二分树”这个热搜词也挺有意思——在硬件描述语言里递归也能用来生成二分结构的电路比如排序网络、比较器树。这说明递归的思想跨语言、跨领域都是通用的。还有“分型递归”像科赫雪花、曼德博集合这类图形天然就是用递归规则生成的每一层都按照同样的缩放规则去绘制。递归在这里的价值是“用极少的代码表达极度复杂的结构”。5.4 练习建议怎么把递归穷举练成肌肉记忆递归穷举这种技能光看文章是学不会的。我的建议是找一组递进式题目把“选择-递归-撤销”这套模板刷到不看代码也能默写出来第一个阶段子集枚举。给定数组输出所有子集。这是最基础的模板题。第二个阶段组合求和。在子集基础上加入“和等于 target”的约束体会剪枝。第三个阶段全排列。引入 used 数组体会“顺序敏感”带来的不同。第四个阶段N 皇后、数独。在更复杂的约束条件下设计剪枝逻辑。每刷一道题都试着手动画出搜索树的前两层再对照代码。走完这个过程你对递归穷举的理解会非常扎实。我个人在实际操作中的体会是递归穷举看起来像一门“玄学”但只要老老实实套模板、画搜索树、想清楚状态与撤销这三件事它就变成了一门技术。特别是“撤销”这一步千万别偷懒——状态没有还原一切都白搭。最后再分享一个小技巧写递归函数的时候先把出口base case写出来再写选择逻辑然后写递归调用最后立刻写撤销。四个步骤固定顺序能帮你少改一半的 bug。这个内容后续还可以这样扩展当你熟练掌握递归穷举之后再去看动态规划很多“重叠子问题 状态转移”的套路本质上就是在递归穷举的基础上加了记忆化——所以你今天啃下的这块硬骨头以后会让你学什么都快。