开篇三道题把回溯算法的老底摸透了代码随想录算法训练营第22天这一天的题单是三道看起来选得很随意的题77. 组合、216. 组合总和III、17. 电话号码的字母组合。但等你真把这三道题刷完、复盘、再横向对比一遍就会发现它们其实是回溯算法专题里最经典的“入门三连”一环扣一环把回溯算法最核心的套路、剪枝思路、递归结构全给铺开了。如果你之前刷题遇到回溯就发怵或者总在递归出口、for循环范围、startIndex和index之间绕晕那这一篇文章建议先收藏再往下看。我一开始刷这三道题的时候也有个错觉觉得77题简单216题就是套模板17题不过是个映射表的事。结果真正落笔去写、去跑、去对比剪枝前后的差异之后才发现自己之前的理解有不少地方是模糊的。今天就以这三道题为主线把回溯算法的整体设计思路、每道题的细节实现、剪枝优化怎么推导、以及我实际踩过的坑一次性讲透。这套内容适合谁适合正在刷LeetCode但被递归回溯反复摩擦的新手也适合刷完题想加深理解、搞清楚“为什么这样写”的进阶选手。如果你打算把组合类型问题、子集问题、排列问题一网打尽那这三道题更值得沉下心好好吃透。1. 内容整体设计与思路拆解1.1 为什么是这三道题它们到底在解决什么先从宏观角度看这三道题在讲什么。77. 组合输入是n和k要你从1到n这n个数字里选出k个数字返回所有组合。注意“组合”二字意味着{1,2}和{2,1}是同一种结果顺序不敏感。这是回溯算法里最基础、最干净的一道“选或不选”类问题也是理解for循环嵌套递归这个最基础结构的窗口。组合总和III输入是k和n要你用1到9这九个数字凑出k个数使得这k个数的和恰好等于n每个数字最多用一次。它其实是77题的一个变体同样是从一个数字集合里选k个数只不过额外多了一个“总和等于n”的约束。这个约束的价值在于它逼着你思考剪枝——不是所有分支都需要走到最后再判断而是可以在中途就判断这条路还有没有可能走到终点。电话号码的字母组合输入是一个数字字符串比如23输出2对应abc、3对应def所有可能的字母组合。表面上看起来和前面两道题很不一样因为不再是“从n个数里选k个”而是“多个集合之间做笛卡尔积”。但本质上一模一样回溯的层数由输入长度决定每一层for循环遍历的是当前数字对应的那一组字母。这三道题放在一起刚好覆盖了回溯算法的两类经典模型组合选择型和多路分叉型。而且它们的难度递进非常平滑77题先让你看懂最基础的树形结构216题在这个结构上引入剪枝17题又把树的形状从“等比缩小”变成了“恒定层数、分支数可变”。刷完这三道题你对回溯的理解才算真正落地。1.2 回溯算法的核心结构递归模板是怎么来的回溯算法本质上是一个“暴力搜索”的优化版或者说它的底子就是深度优先搜索DFS只不过它在搜索过程中记录了“当前路径”并且能够在确定这条路不可能得到正确结果时提前返回不一条道走到黑。这里我先给出一个最通用、也是代码随想录里反复强调的回溯模板后面三道题全部基于这个模板变形void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果; } }这个模板的理解难点有两个。第一个是“for循环负责横向遍历递归负责纵向遍历”。for循环是在同一层里尝试不同的选择递归则是在选定当前选择后继续进入下一层决定后续的选择。两者一配合就形成了一棵完整的递归树。第二个是“回溯撤销处理结果”这行。很多人第一次写回溯最大的疑问就是为什么要撤销我明明把元素放进path了为什么要再pop出来核心原因在于path是一个被反复复用的全局状态。当你在某一层尝试完“选1”这个分支后如果不把1从path里移除那么尝试“选2”这个分支时path里就会残留一个1导致结果错乱。撤销操作就是让path在每一层尝试不同选择时都保持一个正确的“前缀”状态。我见过很多初学者卡在回溯上不是因为递归不懂而是因为没想清楚“同一路径共享path”这件事。你在草稿纸上画出递归树然后把path想象成一根从根节点出发、不停伸长和缩回的绳子就好理解多了。选一个节点绳子伸长递归返回绳子缩回再选另一个兄弟节点绳子再往另一个方向伸长。1.3 组合问题为什么要用回溯而不是多重for循环有人可能会问组合问题不是可以用多重for循环解决吗比如从5个数里选3个就写三层for循环不就行了这样做在k很小的时候确实可以但k一旦变成一个变量比如从20个数里选10个你不可能写10层for循环。而回溯算法厉害的地方在于它的递归层数恰好就是组合个数k通过递归来实现“动态层数的for循环”。这就是回溯算法的核心价值它把“写多少层循环未知”的问题转化成了“递归多少层由参数决定”的问题。另外还要区分一下组合和排列。组合不考虑顺序所以{1,2}和{2,1}算同一个排列考虑顺序两者算不同结果。组合里为了保证不重复我们会在每层递归里传一个startIndex保证下一层选择只能从当前元素后面开始这样天然就规避了重复组合的产生。理解了这一点后面写77题的时候就会明白为什么每一层for循环的起点不是0而是startIndex。2. 第77题组合。经典回溯模板的第一口肉2.1 题目拆解与最基础写法77题输入n4, k2的话输出就是[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。注意没有[1,1]这种重复使用也没有[2,1]这种顺序反过来的。为什么没有重复使用因为组合问题里每个数字只能选一次递归进入下一层后for循环起点要往右移一位。为什么没有“顺序反过来”的结果因为startIndex的机制保证了我们永远只向后取数。来看最基础的实现class Solution { private: vectorvectorint result; vectorint path; void backtracking(int n, int k, int startIndex) { if (path.size() k) { result.push_back(path); return; } for (int i startIndex; i n; i) { path.push_back(i); backtracking(n, k, i 1); path.pop_back(); } } public: vectorvectorint combine(int n, int k) { result.clear(); path.clear(); backtracking(n, k, 1); return result; } };这里面有几个细节要特别注意path.size() k就是终止条件。题目要求取出k个数一旦path里装满了k个元素就说明一条完整路径走完了把path存入result。递归调用时传的是i 1而不是startIndex 1。这里非常关键。i是当前层for循环选中的那个数字下一层的搜索必须从i的下一个数字开始才能保证不会重复使用i也不会回头去找比i小的数字。如果你写成startIndex 1那下一层可能会重复使用之前已经选过的数组合就会大量重复。path.pop_back()就是前面说的撤销操作把刚才放进去的数字拿出来让path恢复到进入这一层之前的状态从而为尝试下一个i做准备。我第一次写这道题的时候就在递归参数那里踩了坑把i 1写成了startIndex 1结果输出了一堆重复组合。排查了很久才发现问题不在终止条件而在递归传参。这个细节一定要刻在脑子里向下一层传的永远是“当前选了i之后剩余集合的新起点”也就是i 1。2.2 剪枝优化到底在优化什么上面这版代码已经能通过LeetCode了效率也不算差。但既然代码随想录里专门讲了剪枝我们就要把这部分吃透。剪枝的本质是提前判断某个分支不可能产生有效结果直接跳过不去递归。77题里一个最经典的剪枝条件出现在for循环的终止范围上。当前已经选了path.size()个元素还需要再选k - path.size()个元素。而从i开始到n为止一共有n - i 1个元素可选。如果n - i 1都不够满足“还需要的个数”那这个分支就算走到头也凑不齐k个数直接终止循环就行。所以for循环的条件可以从i n剪枝为for (int i startIndex; i n - (k - path.size()) 1; i)这个表达式怎么理解n - (k - path.size()) 1表示的是“为了保证从i到n的元素个数不少于还需要的个数i最大能取到多少”。举个例子n5, k3当前path是空的path.size()0还需要的个数是3那么允许的i最大就等于5 - 3 1 3。也就是说第一层的for循环只需要从1遍历到3就行了。为什么不是4和5因为如果第一层选了4剩下的数字只有5一个根本凑不够3个数所以4和5开头的所有分支都注定失败剪掉。再看一个更极端的例子n5, k4当前path里已经有了[1]path.size()1还需要的个数是3那么i最大等于5 - 3 1 3。在第二层i从2遍历到3就够够的了。为什么第二层不能选4因为选了4以后后面只剩一个5凑不够4个数。剪枝优化的效果在数据规模小的时候看不出来但一旦n和k的差距拉开效果非常明显。它能把大量注定失败的无效分支在进入递归前就拦截掉减少递归调用次数也就减少了时间开销。这里还有一个实操心得剪枝表达式的写法不应死记硬背而是要能推导出来。每次写的时候你只需要问自己三个问题现在还差几个元素我从i到末尾还能拿到几个元素如果可拿到的数量小于还差的数量还有必要继续循环吗能把这三个问题想明白剪枝公式自然就写出来了。2.3 组合题和子集题、排列题的本质区别很多刷题的人会在77题之后紧接着遇到78题子集和46题全排列容易把三者搞混。这里我顺手梳理一下帮大家建立一个更完整的坐标系。组合选取k个元素不要求顺序{1,2}和{2,1}等价。核心是startIndex横向限制每次递归从i1开始。子集本质是收集递归树的所有节点而不是只在叶子节点收集。所以子集题的终止条件往往不是path.size() k而是直接在每个递归入口把path存入result。排列顺序敏感{1,2}和{2,1}是不同结果。所以不能靠startIndex来避免重复而必须使用一个used数组来标记某个元素是否已经在当前路径里被用过。这三类题的代码看起来只有细微差别但背后的思维模型完全不同。刷77题的时候先把“组合”这个模型的边界摸清楚后面学子集和排列会轻松很多。3. 第216题组合总和III。在经典模板上长出剪枝的翅膀3.1 题目拆解与基础实现216题的输入是k3, n7输出是[[1,2,4]]。解释一下从1到9里选3个数这三个数之和要等于7。124确实等于7且没有其他组合满足条件。这题和77题的结构几乎一样。如果把77题的n固定为9再额外加一个“总和等于n”的约束就变成216题了。来看代码class Solution { private: vectorvectorint result; vectorint path; void backtracking(int k, int targetSum, int sum, int startIndex) { if (path.size() k) { if (sum targetSum) result.push_back(path); return; } for (int i startIndex; i 9; i) { sum i; path.push_back(i); backtracking(k, targetSum, sum, i 1); sum - i; path.pop_back(); } } public: vectorvectorint combinationSum3(int k, int n) { result.clear(); path.clear(); backtracking(k, n, 0, 1); return result; } };这里的思路是在递归过程中维护一个sum变量它代表当前path里所有数字的和。每往path里放一个数字i就把i累加到sum上递归返回后再把i从sum里减掉。这样当path.size() k时如果sum等于targetSum就把path存入结果。这个做法的好处是直观、好理解也是初学阶段最推荐的方式。但如果你对参数传递比较敏感可能会想到一个优化点不需要在递归中不断加减sum而是直接让targetSum在递归中递减。也就是说每选一个数字i就把targetSum减去i等path.size() k时如果targetSum刚好变成0说明凑齐了。这样就可以少维护一个变量代码也更简洁一些。3.2 剪枝的两个方向和超标与数量不够216题和77题最大的不同在于它拥有两个独立的剪枝维度。第一个维度是“和”的维度第二个维度是“剩余数量”的维度。第一个剪枝如果当前sum已经大于targetSum那后面无论再怎么选正数总和只会越来越大绝对不可能等于targetSum了所以直接return不需要继续递归。对应到代码里可以在进入for循环前加上判断if (sum targetSum) return;注意这个剪枝写在for循环之前代表如果当前这条路径的和已经超标那么这一整个分支都要被放弃。这是一个非常大的剪枝在targetSum较小的场景下能减少大量无效搜索。第二个剪枝和77题一样剩余可选的数字个数必须要满足还差的个数for (int i startIndex; i 9 - (k - path.size()) 1; i)这个表达式和77题的一模一样只不过把n换成了9。含义就是如果从i到9的数字个数已经不足以填满路径那就直接结束循环。两个剪枝合并后的版本class Solution { private: vectorvectorint result; vectorint path; void backtracking(int k, int targetSum, int sum, int startIndex) { if (sum targetSum) return; if (path.size() k) { if (sum targetSum) result.push_back(path); return; } for (int i startIndex; i 9 - (k - path.size()) 1; i) { sum i; path.push_back(i); backtracking(k, targetSum, sum, i 1); sum - i; path.pop_back(); } } public: vectorvectorint combinationSum3(int k, int n) { result.clear(); path.clear(); backtracking(k, n, 0, 1); return result; } };写到这里我想多说一句剪枝不是背出来的而是“画图看出来的”。我在刷这道题的时候拿到题目先没写代码而是在纸上画出k4时的一小棵递归树然后用不同颜色的笔标出了哪些分支根本走不到叶子节点。标完以后你会发现剪枝条件就是从这些“注定失败的边”里归纳出来的。这个习惯我后来一直保留着遇到复杂的回溯题先画树再写代码效率反而更高。3.3 216题为什么容易出错sum的维护时机216题刷的时候最容易出错的地方不在剪枝而在sum的维护上。新手常见的错误写法是把sum的加减顺序搞反甚至忘记在递归返回后做减法。比如有的人会这样写path.push_back(i); sum i; backtracking(k, targetSum, sum, i 1); path.pop_back(); sum - i;看起来只是换了一下顺序对不对其实也没错只要push和sum累加在递归之前完成pop和sum还原在递归之后完成顺序并不严格要求同步。但如果出现下面这种情况就会出bugsum i; path.push_back(i); backtracking(...); sum - i; // 忘记 path.pop_back()path里残留元素sum也维护错误最终结果就会多出一堆错误组合。所以我个人的习惯是在写回溯递归体时所有“添加状态”的操作放在递归调用之前连续写完所有“还原状态”的操作放在递归调用之后连续写完中间不留任何其他语句。这样即使代码出错了排查的注意力也可以集中在某两个连续区块不会东找西找。另外还有一个细节result.push_back(path)这一步一定要放在终止条件里而不是放在path.size() k sum targetSum的外面。如果放在外面那么即使sum不满足条件也会把path存进去导致结果里出现大量不满足和为n的组合。3.4 话题延伸组合总和系列的其他变体216题刷完以后紧接着会遇到39题“组合总和”和40题“组合总和II”。前者允许同一个数字无限次重复选取后者要求数组中有重复元素但每个元素只能用一次并且结果不能重复。为什么在这里提这两个题因为它们的解法全都是在216题这套模板上加细节。39题把递归传参i 1改成i就允许数字重复使用了40题在9个数字的基础上改成处理一个可能有重复元素的数组并且通过树层去重来避免结果重复。刷完这三道组合总和系列你对回溯里的“去重”和“剪枝”基本就建立起了整体认知后面无论遇到什么组合类问题都能迅速定位到对应的模板和改法。4. 第17题电话号码的字母组合。从组合选择到多路映射4.1 题目分析与数据结构建模17题的输入是一个由2到9组成的数字字符串比如23。数字2对应abc数字3对应def题目要求输出所有可能的字母组合。[ad,ae,af,bd,be,bf,cd,ce,cf]。这道题从表面上看和前面两道完全不同不再是数字集合里选几个数而是多个集合之间做组合。但仔细一想它同样是回溯只是递归树的形状变了。先要解决一个基础问题数字到字母的映射怎么记录最直接的做法是定义一个字符串数组下标对应数字const string letterMap[10] { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz };注意letterMap[0]和letterMap[1]都设为空字符串因为电话键盘上0和1没有对应字母。2对应abc3对应def7和9分别对应四个字母这一点也和普通数字不同。建模完成之后回溯的框架就和前面一样了层数是输入字符串的长度每层for循环遍历的是当前数字对应的字母集合。4.2 基础实现层数由digits长度决定class Solution { private: const string letterMap[10] { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; public: vectorstring result; string s; void backtracking(const string digits, int index) { if (index digits.size()) { result.push_back(s); return; } int digit digits[index] - 0; string letters letterMap[digit]; for (int i 0; i letters.size(); i) { s.push_back(letters[i]); backtracking(digits, index 1); s.pop_back(); } } vectorstring letterCombinations(string digits) { result.clear(); s.clear(); if (digits.size() 0) return result; backtracking(digits, 0); return result; } };这段代码里有几个地方要重点看index代表当前处理到digits的第几个字符。终止条件是index digits.size()说明所有数字都已经被映射成一个字母此时s就是一个完整的结果。每一层for循环遍历的不是从startIndex开始的数列而是当前数字对应的字母集合。所以for循环的起点是0不是startIndex。这一点和77题、216题有本质区别77题里每层可选数字的范围是不断缩小的而17题里每个数字对应的字母集合彼此独立选择范围不需要收缩。传参是index 1而不是i 1。因为index表示digits的位置进度和当前选了哪个字母无关。这个细节也容易写错如果写成i 1那就会越过了原本应该处理的digits位置后续递归就会错乱。另外有一个必须注意的空输入处理。如果digits是空字符串那么按逻辑来说应该输出空列表但如果不提前判断backtracking会直接进入index0、digits.size()0直接相等result会被push_back一个空字符串[]这就不符合题意了。所以要在letterCombinations函数里先判断一下如果digits为空直接返回空result。4.3 index和startIndex是两回事千万别混我观察到很多人在回溯里最容易搞混的就是index和startIndex到底什么区别。这两者虽然都用来控制递归进度但控制的东西完全不同。startIndex是“同一集合内”的选取起点它决定了下一层递归的for循环从哪个位置开始遍历目的是排除已经选过的元素避免组合重复。77题和216题使用的就是startIndex。index是“不同集合之间”的处理进度它决定了当前递归需要处理的是输入序列中的哪一个位置并不限制for循环的起点。17题使用的就是index因为每个数字对应的字母集合是独立的for循环从头遍历一遍就好。对于组合类问题你用的是startIndex对于排列类问题、多集合映射类问题你用的是index或者used数组。如果混淆了这两个参数代码就会出现一些非常诡异的错误。比如把77题的递归传参随意改成index你会发现path可以重复使用同一个数字结果出现大量[1,1]这样的组合。我自己的排查方法是在写每一道回溯题时先问自己一个问题——递归树的不同层之间可选集合有没有交叉如果有交叉并且不能重复选就需要startIndex把交叉区域通过起点移动来消除如果没有交叉或者每个层级的可选集合完全独立那用index就够了。4.4 17题的复杂度分析思路17题的时间复杂度分析也是一个常被忽略的考点。假设输入字符串的长度是n其中包含m个对应4个字母的数字7和9其余n-m个数字对应3个字母。那么总的组合数量就是3^(n-m) * 4^m。每一层递归都需要处理当前字母字符串并且最终要把长度为n的字符串拷贝进result所以总时间复杂度大约是O(n * 3^(n-m) * 4^m)。这里有个容易误解的地方不是所有数字都对应4个字母所以不能简单写成O(4^n)。这也是为什么面试里喜欢问17题复杂度——它考察的是你是否能根据输入的具体构成来精确估算而不是只会背复杂度公式。另外这道题还可以用队列的方式解决也就是先建立一个初始队列逐个读取数字每读取一个数字就把当前队列中的每个字符串分别拼接上该数字对应的所有字母生成新的字符串重新入队。这种BFS写法和回溯的DFS写法各有优劣。回溯版代码结构统一方便后续套模板队列版空间占用在某些情况下可能更高但对于很多没接触过回溯的人来说可能更好理解。我个人还是推荐先用回溯写因为这一天的训练目标就是吃透回溯。5. 三道题横向对比从递归树看透回溯的统一性5.1 递归树的形状对比这三道题都使用回溯为什么有的人刷完之后能举一反三有的人却在面对新题目时依旧一头雾水我觉得最核心的差别在于有没有从递归树的角度去理解它们。77题的递归树是这样的第一层有n个分支每个分支进入第二层后可选集合都缩小了。从根到每个叶子节点路径长度固定为k整棵树呈现“逐层收窄”的形状。216题的递归树和77题长得很像只是额外带上了一个sum约束。如果你把“sum大于targetSum”的分支全部剪掉树会变得稀疏很多。这棵树里很多本来可以长到k层深的路径在中途就被截断了。17题的递归树则完全不同它的层数固定为digits的长度而每一层有多少个分支取决于当前数字映射到几个字母。有的层分3叉有的层分4叉是一棵“层间分支数不一致”的树。如果你能在脑子或者草稿纸上把这三棵树的形状画出来你就会发现回溯算法的本质其实就是在这棵树上做深度优先搜索并且在搜索过程中维护路径、判断终止、必要时剪枝。模板再怎么变底层逻辑都没跳出这个框架。5.2 一个模板吃透组合类题目把三道题打完可以沉淀出下面这些“条件反射”看到了“组合”“选出k个”“返回所有方案”这类关键词立刻想到回溯空间复杂度也可以接受暴搜的规模。如果题目是从一个集合中选取且顺序不重要立刻准备startIndex参数递归传i 1。如果题目有额外约束比如总和等于某个值、总和不超过某个值立刻思考“约束能不能在进入递归前就判断”能就剪枝。如果题目是多组数据之间做组合立刻把层数锁定在输入长度上用index控制层数每层for循环遍历当前组的所有可选值。这套条件反射建立起来以后很多题目虽然你没见过但只要照着这个思维路径走一圈基本能确定该用回溯并且知道该怎么写。5.3 从这三道题看代码随想录的训练节奏代码随想录的安排有一个很明显的特点先在最简单的组合题上建立回溯模板的肌肉记忆然后立刻用组合总和III逼你思考剪枝再用电话号码的字母组合逼你转换思维模型。这个节奏踩得非常准没有一上来就扔一道hard级别回溯题把你打懵而是用三道题的时间让你经历“模仿模板→优化模板→跳出模板”的完整历程。在我自己的刷题复盘里第22天这个打卡节点的价值不只是学会三道题更重要的是为后续的39题组合总和、40题组合总和II、46题全排列、47题全排列II、78题子集等一系列回溯问题打下了同一个底座。只要把这一天的内容消化到位后续的回溯题大部分都只是在这个底座上做微调。6. 常见问题与排查技巧实录6.1 输出结果为空或者输出了一堆重复组合这是回溯新手最常见的问题。如果你发现结果为空首先要检查终止条件是否写对。77题的终止条件是path.size() k但如果你把result.push_back(path)放在了终止条件外面甚至完全忘了写终止条件递归就会一直往深处走永远收集不到结果。如果你发现结果里有大量重复组合比如[1,2]和[2,1]同时出现那几乎可以断定你在递归传参时没有正确使用i 1。要么写成了startIndex 1要么干脆写成了startIndex导致下一层可以重复或回头选择元素。修复方式很简单把递归参数改成i 1让下一层的搜索起点严格从当前选中元素的下一个位置开始。6.2 剪枝条件到底放在for循环前还是循环内这是一个很具体、也经常让人纠结的问题。我的建议是如果剪枝是对整条路径的可行性判断就放在for循环之前比如216题的sum targetSum如果剪枝是对某个具体分支的可行性判断就放在for循环的边界条件里比如77题的i n - (k - path.size()) 1。前者是“当前路径还能不能走”后者是“当前层的这个分支还值不值得走”。两者解决的问题层面不同位置自然也不同。如果你放反了比如把sum targetSum放在for循环里在每一轮循环开始前判断也能生效但逻辑上不够干净而且容易漏掉那些连for循环都不用进入就已经超标的路径。6.3 为什么我的代码在LeetCode里超时回溯算法本身是暴力搜索如果没做剪枝在大数据量下超时是正常现象。如果你遇到超时优先检查两件事第一件事是for循环范围是否已经使用剪枝表达式。如果还是i n这种全量遍历建议改成i n - (k - path.size()) 1这个优化立竿见影。第二件事是递归时是否重复做了很多无意义的拷贝。比如有的写法会在参数里直接传vector导致每层递归都拷贝一次数组开销巨大。正确的做法是把result、path这类需要频繁修改的容器设为类的成员变量递归时只传下标和起始位置等基础类型的参数避免不必要的拷贝。6.4 画递归树的实操方法最后分享一个我刷回溯题时一直在用的方法画递归树。具体操作是拿到一道回溯题先不写代码取一个最小的输入用例比如n3, k2然后从根节点开始一层一层把递归树画出来。每画一层就标注一下“进入这一层时startIndex是多少”“path当前是什么”。画完之后终止条件、for循环范围、剪枝条件其实都已经摆在纸面上了。照着自己画的树写代码正确率会高很多。这个方法对新手特别管用。因为在画树的过程中你会被迫去想清楚每一层在遍历哪些选择下一层还能选哪些哪些分支根本不需要走到叶子三个问题想明白了代码基本上就顺手写出来了。三道题刷下来我自己最深的体会是回溯算法的难度不在理解递归而在理解“状态如何在递归中传递、在回溯中恢复”。只要把递归树的图景牢记在心把startIndex和index的区别分清楚把剪枝的时机想清楚那么以后再遇到任何组合类、子集类、排列类的问题你都能下意识地写出那套模板并根据题目的特殊约束去调整细节。第22天的这三道题正是帮我们把这件事练成肌肉记忆的起点。