在开始之前

⚡ 30 秒速记

• 递归回溯不是玄学，它就是「做选择 → 往下走 → 撤销选择」的穷举套路
• 门槛主要在心理上：一看到「思想」两个字就先吓住了
• 学法：从最小的例子手推，比如两个数的全排列，看每一层做了什么
• 先能写出能跑的小例子，再回头补术语和定义
• 一道题会了不算，换一道同类题还能写出来才算

递归回溯听起来唬人，其实就是一套能反复套用的穷举套路，难的是第一次跨过心理门槛。 很多人一看到「思想」就觉得是一大坨理论，还没开始看题就先放弃了。我的建议是别从定义入手，拿一个最小的例子手推一遍，比如 [1,2] 的全排列，每一层选了谁、什么时候返回、返回后数组变成什么样，在纸上画出来。画清楚一次，后面的组合、子集都是换汤不换药。

根据我深耕技术写作多年的经验，很多同学一看到标题里有“思想”两个字，就会觉得接下来要讲的一定是一个非常复杂的“高大上”理论，于是他会先给自己箍上一个“我一定学不会”的紧箍咒，接着心里就开始打退堂鼓了。这样的同学在和算法正面交锋之前，就先被自己内心的恐惧击垮了，实在可惜。

站在讲解者的角度来说，我确实不会先给大家画个饼，说这玩意儿有多么多么简单——这是一个非常不负责任的承诺。因为对于初学者来说，没有什么是简单的，从不会到会本来就是一个过程。况且，你现在学的是不少前端er都不肯学/学不动的算法，这本就不是一个轻松的挑战。但既然走到了这一步，不管你这会儿心里有多慌，我都希望你可以坚持一下、读读看，你会发现这玩意儿真的不是玄学——它真的很香。

💬 面试官追问

• 能背出回溯的定义，但说不清 path 为什么一会儿变长一会儿变短，说明什么？

  说明还没把概念对上执行过程。让他拿 [1,2] 手推一遍，每次 push 和 pop 时 path 是什么写在旁边，推完基本就通了。

• 新人非要先把递归理论读完再动手，两天了还写不出最小例子，怎么办？

  直接给一道输入很小的题，先写出能跑的版本，再对着代码讲「这行就是选择、这行就是撤销」。理论在有了具体代码之后再补，吸收快很多。

• 面试时候选人一听回溯就紧张，你会怎么引导？

  先让他写两个元素的全排列，规模小、分支少，写出来信心就有了。能写通再加约束，比如去重或者限定长度；连递归终止条件都不清楚的话，扩题也没意义。

• 说「算法太玄学只能背模板」，换一道题就不会了，问题在哪？

  模板只是把已经理解的东西压缩了一下，没理解就背，约束一变就不知道改哪。要能说出每层有哪些候选、什么时候结束、返回后状态怎么恢复，这三点说清楚了，模板自己就能推出来。

如何学好这一节

⚡ 30 秒速记

• 面试不考背定义，考能不能把题做出来 → 以题为纲
• 先手画搜索树的前两层：每层有哪些候选、哪些分支该剪
• 模板里的参数各管一件事：path 记当前选择，start 管不回头，used 管不重复，remain 管剩余目标
• 用最小输入逐步跟踪，再拿空输入、重复元素、无解验证边界
• 「思想」本质是套路，吃透一个能带走一大批题

这一节别纠结什么是递归、什么是回溯，直接做题，从题里认识套路。 面试里算法几乎不考背概念，看的是你能不能把题写出来。我的做法是遇到「列出所有方案」的题，先在纸上画出搜索树的前两层，看每一层在做什么重复的选择、什么时候停。画出来之后，代码里的 path、start、used 分别对应什么就很清楚了。刚开始想不到递归很正常，做完全排列、子集、组合这三道，自然会形成条件反射。