刷算法题最怕的不是题目难而是觉得“今天又碰上了新题型”。实际上很多题翻来覆去就是那几个套路尤其是回溯这块。训练营第十九天我拿到的三道题是77.组合、216.组合总和、17.电话号码的字母组合。单看题面一个是选数字、一个是求和、一个是字符串映射感觉完全不搭边。真上手写一遍就会发现它们共用同一套回溯模板只是改改参数、改改剪枝条件而已。这篇文章就把我当天刷完这三道题之后的完整思路、代码模板、剪枝推导过程以及踩过的坑都整理出来给同样在刷回溯题的同学一个能直接照抄的参考。1. 三道题放一起到底在练什么1.1 回溯算法解决的核心问题先聊一个很多人会忽略的点回溯到底在解决什么问题一句话总结回溯本质上是“暴力枚举”的优雅写法。比如你要在 1 到 9 里选 3 个数最笨的办法就是写三层 for 循环。但万一要选 5 个数呢选 k 个数呢k 是变量你不可能在代码里写 k 层循环。这时就需要“递归里的循环”来代替这种不固定的多层循环每一层递归处理“选第几个数”递归层数由要选几个数决定。回溯的过程可以理解成走迷宫往前走一步发现这条路可能走通就继续走发现走不通就退回来换另一个方向再试。这个退回来的动作在代码里就是“撤销选择”。所以回溯题的代码几乎都有一个特征递归调用前后各有一行“选择”和“撤销选择”的代码成对出现这就是网上常说的“回溯三件套”。1.2 三道题的共同套路这三道题放在同一天我个人理解是它们在帮大家练同一件事把“在多条路径里做选择”的问题统一转化成回溯模板。77.组合从 1 到 n 中选 k 个数要求不重复、不讲究顺序。核心是“同一集合内选元素”所以递归时要用一个 startIndex 控制下一次只能从当前位置后面开始选避免出现重复组合。216.组合总和和 77 几乎一样但多了一个“和必须等于 n”的条件。它在 77 的基础之上多维护一个 sum 变量同时多出来一种“总和超出目标就提前返回”的剪枝。17.电话号码的字母组合看起来完全不一样要从数字对应的字符串里选字母。但本质上也是从集合里选元素只不过每一次不是在同一个集合里选而是“按位置”从不同的集合里选。所以它不需要 startIndex只需要一个 index 记录当前处理到第几个数字。三题做完你就能理解一句话回溯模板是骨架约束条件才是灵魂。题目怎么变都是在模板上做加法。1.3 先把这个模板印在脑子里我用 C 写一个最通用的回溯模板后面所有题都是在这个基础上改void backtrack(参数) { if (终止条件) { 存放结果; return; } for (选择 : 本层集合中元素) { 处理节点; backtrack(递归调用); 撤销处理结果; } }看着简单但里面有几个关键问题终止条件写什么for 循环从哪里开始递归参数怎么传撤销要撤到什么程度这些细节在每道题里不一样但只要你把模板背熟做题时就是在往里填东西。提示我在刷题初期犯过的最大错误是“背题”而不是“背模板”。遇到新题就想着回忆自己写过哪道相似的结果题目一变就蒙。回溯题的复习重点应该是拿到题先判断“递归树长什么样”然后照着模板往下套。2. 77. 组合先吃透回溯模板和剪枝2.1 为什么不能用多层 for 循环硬写77 题的要求是给定两个整数 n 和 k返回范围 1 到 n 中所有可能的 k 个数的组合。比如 n4k2输出就是 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。如果 k 固定等于 2确实可以写两层循环for (int i 1; i 4; i) { for (int j i 1; j 4; j) { cout i , j endl; } }但题目里的 k 是动态的可能等于 2也可能等于 3、5、10。你不可能写 10 层循环。这时候就要借助递归让“递归层数”替你做“循环层数”。第一层递归决定第一个数第二层递归决定第二个数第三层递归决定第三个数……递归到第 k 层时就获得了一个长度是 k 的组合。2.2 套模板写出第一版先看完整代码再逐段解释class Solution { private: vectorvectorint result; vectorint path; void backtrack(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); // 选择当前数字 backtrack(n, k, i 1); // 递归选下一个数字只能往后选 path.pop_back(); // 撤销选择回到上一层状态 } } public: vectorvectorint combine(int n, int k) { result.clear(); path.clear(); backtrack(n, k, 1); return result; } };几个细节展开说说。第一startIndex 的作用。组合问题里 [1,2] 和 [2,1] 是同一个结果所以选完 1 之后第二个数只能从 2 开始选不能回头再选 1。startIndex 就是用来做这件事的。它保证了“组合内的数字从左到右是递增的”这样天然就去重了。第二终止条件是 path.size() k。因为组合只关心数量不关心和监督无关的和所以只要收集到 k 个数就说明找到了一条完整路径直接存进 result。第三撤销的成对性。path.push_back(i) 和 path.pop_back() 必须成对出现。每轮 for 循环开始先把 i 加进来递归返回后把 i 弹出去然后 i 进入下一个选择。如果没有 pop_backpath 就会越积越长最后所有结果全部错乱。注意写递归函数时形参里的 n 和 k 其实从第一层到最后一层都没变过真正在变的是 startIndex 和 path。你可以在脑子里想一棵树根节点是 startIndex1每往下走一层可选范围就逐渐收窄叶子就是长度为 k 的 path。2.3 剪枝是怎么推出来的第一版代码能通过但效率不高。比如 n4k4第一个数选 2 之后就只剩 [3,4] 两个数就算全部选上也凑不够 4 个数这条分支根本没必要继续走。剪枝的核心思想是当前剩余可选数字不够填满 path 时直接结束循环。需要满足的条件是从 i 到 n 的数字个数加上 path 里已有的数字个数至少等于 k。也就是n - i 1 k - path.size()移项得到i n - (k - path.size()) 1所以 for 循环可以优化成for (int i startIndex; i n - (k - path.size()) 1; i) {很多初学者容易把边界写成n - k path.size() 1之类的错误版本。我教你一个验证方法当 path 为空、k2、n4 时i 的最大值应该是 3因为从 3 开始还能选到 4如果 i 等于 4后面没有数能组成长度为 2 的组合了。把 k2、n4、path.size()0 代进n - (k - path.size()) 1得到 4 - 2 0 1 3刚刚好。以后不确定就带边界值验一下。2.4 手推一次 n4k2我刷题时有个习惯新题必须手动模拟一次递归过程不然看代码总觉得隔了一层。这里简单模拟一下backtrack(n4, k2, startIndex1)i1path [1]递归进入 backtrack(startIndex2)i2path [1,2]长度等于 2存入 result返回i3path [1,3]存入 result返回i4path [1,4]存入 result返回i2path [2]递归进入 backtrack(startIndex3)i3path [2,3]存入 resulti4path [2,4]存入 resulti3path [3]递归进入 backtrack(startIndex4)i4path [3,4]存入 resulti4path [4]进入递归后 startIndex5for 循环 54 不成立直接返回最后 result 就是 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。注意循环到 i4 时不会再往下选因为后面没有数字比 4 更大这也是 startIndex 的另一个作用保证不出现重复组合。3. 216. 组合总和多一个约束多一层剪枝先说一个题号细节。训练营标题里写的是“216.组合总和Ⅱ”但 LeetCode 中文站里这题通常翻译成“组合总和 III”题号是 216是组合总和系列里的第三题。很多笔记和训练营会用“组合总和Ⅱ”来称呼它大家知道指的都是这题就行别被题号绕晕。3.1 题目到底多了一个什么约束216 题要求找出所有相加之和为 n 的 k 个数的组合。组合里只允许含有 1 到 9 的正整数并且每种组合中不存在重复的数字。对比 77这题有两点不同数字范围固定是 1 到 9而不是 1 到 n。除了“选 k 个数”还要保证这 k 个数的和恰好等于 n。换句话说77 的终止条件只有长度判断216 的终止条件变成长度判断加上和判断。这也就意味着递归时需要多维护一个变量 sum记录当前 path 里所有数字的和而不是在终止时重新遍历计算一遍。3.2 代码实现引入 sum 参数class Solution { private: vectorvectorint result; vectorint path; void backtrack(int k, int n, int sum, int startIndex) { if (path.size() k) { if (sum n) result.push_back(path); return; } for (int i startIndex; i 9 - (k - path.size()) 1; i) { path.push_back(i); sum i; backtrack(k, n, sum, i 1); sum - i; path.pop_back(); } } public: vectorvectorint combinationSum3(int k, int n) { result.clear(); path.clear(); backtrack(k, n, 0, 1); return result; } };这段代码里最核心的变化是 sum 的增和减它必须和 path 的增与减保持一致。很多人会把 sum 直接当递归参数传值不手动加加减减这样也行但要注意传参时的值传递在每一层递归里都是独立的回溯时其实不需要额外减回去。我这里为了直观选择手动维护。3.3 两层剪枝和超了就返回、循环右边界这题能剪枝的地方比 77 更多我就靠这个把运行时间从 20ms 压到了 4ms 左右。第一层剪枝sum 超过目标值 n 时直接终止当前分支。这里要小心因为数字都是正数再加下去只会更大不可能回到 n所以可以提前 return。if (sum n) return;注意这行代码的位置一般放在递归函数的最前面和终止条件并列。位置放错会漏剪。第二层剪枝循环右边界和 77 一样数字范围固定是 1 到 9所以把 for 循环右边界改成9 - (k - path.size()) 1确保后面的数字够用。第三层其实还有一个更细的剪枝在循环里如果sum i n因为 i 是递增的再往后更大直接 break。这个剪枝在 n 比较小、k 比较大的时候效果特别明显。for (int i startIndex; i 9 - (k - path.size()) 1; i) { if (sum i n) break; // ... }3.4 一个完整示例k3n9手动过一遍。初始 startIndex1sum0。i1path[1]sum1递归i2path[1,2]sum3递归i3path[1,2,3]sum6长度 3 但 sum ! 9返回i4path[1,2,4]sum7长度 3 但 sum ! 9返回i5path[1,2,5]sum8不等于 9i6path[1,2,6]sum9存入 result [[1,2,6]]返回i7这时 sum i 3 7 10 9breaki3path[1,3]sum4递归i4path[1,3,4]sum8不等于 9i5path[1,3,5]sum9存入 result [[1,2,6],[1,3,5]]i6sum i 4 6 9breaki2path[2]sum2递归i3path[2,3]sum5递归i4path[2,3,4]sum9存入 result后续 i5 时 sum i 9breaki3path[3]sum3递归i4path[3,4]sum7再选一个最小数字 5sum12 9break最终结果是 [[1,2,6],[1,3,5],[2,3,4]]。注意这个模拟过程里 break 的条件要理解透。进入 i7 时当前 sum3path 为 [1,2]加上 7 是 10肯定超过 9而且后面的数字更大所以 break。这两层剪枝叠加之后很多无效分支根本走不到递归最深处。4. 17. 电话号码的字母组合从“同一集合”跳到“不同集合”4.1 数字到字符串的映射表题目给的是类似 “23” 这样的字符串每个数字对应一组字母2 对应 abc3 对应 def4 对应 ghi……要求输出所有可能的字母组合。比如 “23” 的输出是 ad、ae、af、bd、be、bf、cd、ce、cf。这题的关键第一步是建立数字到字母的映射表。直接用一个字符串数组const string letterMap[10] { , // 0 , // 1 abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz // 9 };这里两个空字符串对应 0 和 1因为这两个数字在电话上没有字母。刷题时可以不管它们但理解映射关系时心里要有数。4.2 和 77/216 的关键区别不需要 startIndex很多同学在从 77/216 跳到 17 时会卡在一个地方为什么这题不用 startIndex原因是77 和 216 里你要选的元素都在“同一个集合”1 到 n或者 1 到 9里。如果选了 1就不能再选 1 之前的数字否则会生成重复组合所以要从 startIndex 开始往后选。但 17 题不一样比如 digits 23第一个字符位置只能从数字 2 对应的 abc 里选第二个字符位置只能从数字 3 对应的 def 里选。每一次选择面对的是一个完全不同的集合不存在“选过的位置还能不能回头选”的问题因为每个 index 都对应唯一的集合。所以 17 题里的递归参数用的是 index表示当前处理到 digits 的第几个字符而不是能选到几号元素。4.3 完整代码和空字符串处理class Solution { private: const string letterMap[10] { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; vectorstring result; string s; void backtrack(const string digits, int index) { if (index digits.size()) { result.push_back(s); return; } int digit digits[index] - 0; string letters letterMap[digit]; for (char c : letters) { s.push_back(c); backtrack(digits, index 1); s.pop_back(); } } public: vectorstring letterCombinations(string digits) { result.clear(); s.clear(); if (digits.empty()) return result; backtrack(digits, 0); return result; } };两个特别容易出问题的地方第一空字符串处理。如果 digits 是空串理论上应该输出空数组 []而不是 []。所以主函数里要先判断if (digits.empty()) return result;否则递归里index digits.size()成立会把s空字符串存进 result得到错误结果。第二char 转 int。digits[index] - 0才能得到真正的数字。我第一次写的时候直接用了int digit digits[index]结果拿到的数字是 ASCII 码比如字符 2 实际是 50再去取 letterMap[50] 直接越界。这类低级错误一定要在代码 Review 时盯住。4.4 用例子走一遍 index 的作用以 digits 23 为例。backtrack(digits, index0)digit 2letters abccasa递归进入 backtrack(index1)digit 3letters defcdsad递归进入 backtrack(index2)index size存入 adcesae存入 aecfsaf存入 af回到上一层弹出 ascbsb…… 以此类推外层循环管第一个字母内层递归管第二个字母。因为题目只需要“按顺序取字母”本质上就是笛卡尔积回溯只是把多层的 for 循环写活了。如果 digits 长度是 4那就相当于四层循环。提示这道题很多人会问“为什么结果顺序是这样的、为什么不是从 b 开始”。原因是 for 循环从左到右遍历第一个字符 c 在 index0 时从 abc 开始所有包含 a 的组合递归完成后才会轮到 b。这是回溯的正常顺序不需要特殊处理。5. 高频报错与避坑清单这几道题刷完我把容易踩的坑集中整理了一下。很多问题不是思路不会而是细节翻车。5.1 递归参数传错把 i 当成 startIndex 传这是回溯新人最高频的错误。正确写法是backtrack(n, k, i 1);错误写法往往是把 i 1 写成 startIndex 1或者不 1 直接传 i。不 1 的后果是下一层还能选当前数字导致结果出现重复元素比如 [1,1,2] 这种传 startIndex 1 的后果是每层递归都是从固定位置开始不是从当前选中的下一位开始会导致组合重复或者漏解。我自己的验证方法是在递归函数入口打印一下当前 startIndex 和 i跑一轮 n4、k2对比输出立刻就能看出来哪里传错了。5.2 撤销步骤漏掉path 越积越长很多人写递归时只记得 push_back忘了 pop_back。这样 path 会在递归返回后越积越多最终结果全是同一串超长数组。回溯里“选择”和“撤销选择”必须对称就像往前迈一步就要退一步不然就走不回原来的岔路口了。5.3 剪枝边界差 1i n - (k - path.size()) 1这个式子最后的 1 特别容易丢。丢了之后的结果是最后一个合法组合可能取不到。比如 n4k2没有 1 时 i 最大只能取到 2只能得到 [1,2]、[1,3]、[2,3] 之类的部分结果[1,4]、[2,4]、[3,4] 全被剪掉了。5.4 结果集没存副本这题里因为是 path 或 s 直接存到 result在 C 里result.push_back(path)默认是深拷贝所以没问题。但如果你用 Java 或 Python直接存引用就会翻车后续pop_back()会把已经存进结果集的数据也改掉。建议在所有语言里都养成“拷贝一份再存”的习惯省心。5.5 17 题漏掉空输入判断17 题如果输入是空字符串需要单独判断。这个问题和第 5.4 类似都属于“边界条件专项检查”。我在刷题时会特意列一张小清单输入为空、输入长度为 1、输入包含 0 和 1 这三种情况都要手动跑一遍。错误类型表现排查方向递归参数传错输出重复组合检查 startIndex 是不是 i 1漏掉 pop_back所有结果一样检查选择/撤销是否成对剪枝边界少 1缺少合法组合代入 k2、n4 验证右边界直接存引用结果集被后续修改存 path/s 的副本空输入未处理多出空字符串结果主函数开头判断 empty提醒这些错误里第 5.1 和 5.2 是最隐蔽的。因为它们不一定会让程序崩溃只是输出不对。我强烈建议新刷回溯的同学第一遍先别追求剪枝把最朴素的模板跑通再一步步加优化。剪枝加错了反而更难排查。6. 最后补充一点刷题节奏上的个人建议第十九天刚好是回溯算法专题的开头后面的子集、全排列、分割回文串、N 皇后基本都能用这几道题的思维迁移过去。我个人的体会是这三道题不要急着追求“做对”而是要做“熟练”。怎么衡量熟练不看题解能够 10 分钟内写出一个朴素回溯版本并解释清楚终止条件、for 循环从哪里开始、为什么这样撤销选择就算过关。具体操作上我建议每天刷题前先默写一遍回溯模板再开始做题。别看这个动作简单它能让你的大脑从“回忆模板”切换到“套模板解题”的模式。等到 20 多天后你刷回溯进阶题时会发现最吃力的阶段永远是“今天该用哪个参数”而不是“这题会不会做”。三题全部能独立手写之后再回头看看这三道题的递归树你会发现它们其实长得一模一样都是多叉树往下走走到叶子判断是不是合法答案不合法就回溯、剪枝。想通这一层训练营第十九天的任务才算真正吃透了。