代码随想录刷到第二十三天今天就三道题39. 组合总和、40. 组合总和II、131. 分割回文串。这三道题放在同一批不是巧合——它们都是回溯算法里的“组合类”问题但层层递进把“能不能重复选”“结果要不要去重”“怎么在字符串上做选择”这三个核心问题全给覆盖了。刷完这三道我对回溯的理解才真正从“会写模板”变成了“知道什么时候该套模板、模板哪里要改”。很多初学者刷回溯背了模板却不会用看到组合总和这种题就开始纠结“这个startIndex到底该传i还是i1”看到分割回文串更是怀疑人生——“这不就是个字符串题吗跟回溯有什么关系”这篇文章我把三道题放在一起拆重点不是贴一遍可以通过的代码而是讲清楚每道题背后的选择逻辑为什么39题能重复取却不会死循环40题为什么要排序加去重131题为什么本质上就是一个切割位置的选择问题。搞懂这些后面刷子集、排列、棋盘类问题会轻松很多。1. 为什么说“组合总和”是回溯法入门的试金石1.1 从暴力枚举到回溯组合问题的本质先看39题的题目形态给一个无重复元素的正整数数组candidates和一个目标值target找出所有和等于target的组合candidates里的数字可以无限重复选取。很多人第一次看到“无限重复选取”会慌这怎么枚举循环层数都不固定。但回溯解决的就是这类“循环层数不确定、每层可选范围会变化”的问题。回溯的本质可以理解成在一棵多叉树上做深度优先搜索。每一层递归对应一次“选数”动作树枝上走的是具体的某个数字树的深度由满足条件的路径长度决定。因为可以重复选同一个数字所以每次递归时下一层还能继续选当前这个下标不需要往后跳。这种场景有个很直观的生活类比你在一家自助餐厅配菜要求凑够一定金额。每道菜可以重复拿你每拿一道菜下一轮还是面对同样一排菜。这就是39题的搜索过程。1.2 39题的两个关键细节startIndex与可重复选取回溯的模板长这样递归函数参数记录当前的状态目标和、已选数字、可选的起始下标每层for循环负责横向遍历递归负责纵向深入终止条件判断是否收集结果。39题代码如下class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint candidates, int target, int startIndex, int sum) { if (sum target) { result.push_back(path); return; } for (int i startIndex; i candidates.size(); i) { if (sum candidates[i] target) break; path.push_back(candidates[i]); backtracking(candidates, target, i, sum candidates[i]); path.pop_back(); } } public: vectorvectorint combinationSum(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0); return result; } };两个坎是新手必踩的。第一个坎是“为什么递归传入的是i而不是i1”。因为元素可以无限重复选取选了candidates[2]之后下一层还需要能继续选candidates[2]所以下一层的起始下标不能跳过当前位置。只有像经典组合问题比如从n个数里取k个那样每个元素只能用一次递归才传i1。如果这里写成了i1你会得到一堆不完整的组合比如[2, 3]能选出来但[2, 2, 2]这种就永远选不出来。第二个坎是“为什么不会死循环”。既然可以无限重复选那递归会不会无限深入不会因为有一个终止条件sum等于target时收集结果并return同时剪枝逻辑也保证了sum只会越来越大一旦加上当前元素超过target就停止。数字是正整数路径总和严格递增递归深度自然有上界。1.3 剪枝不是玄学排序后break的原理推导先想清楚暴力的写法for循环里不应该在sum加上candidates[i]大于target时才continue因为continue会继续遍历后面的元素但后面元素比当前元素更大前提是排过序加上去只会更大永远不可能等于target。所以剪枝的思路是先对candidates排序然后在for循环开头判断如果sum candidates[i] target直接break跳出整个循环。排序的意义就在这——它让数组从左到右递增一旦发现某个元素已经过大后面的所有元素都会更大没有继续遍历的必要。不排序的话小元素可能排在大元素后面你就只能continue而不是break效率差不少。这个剪枝在39题里不是可选项而是必须项。因为candidates里的数字可以重复取暴力递归的搜索空间非常大。我实测过不剪枝在target稍大时会有大量无效递归加上排序和break之后递归次数能少一个数量级。另一个细节递归函数里我用sum做累加也有人用target不断减的方案。两者思路一样但用target递减的方式在判断上更简洁一些——当target已经小于0时直接return。我个人建议写题时统一用一种避免在几种回溯模板之间反复横跳。2. 组合总和II重复元素下的“同层去重”才是真正的分水岭2.1 40题和39题差在哪一个“不能重复选”一个“结果不能重复”40题换了个条件candidates里可能有重复元素但每个数字在每个组合里只能用一次。输出要求所有组合不能重复。这两个表述容易混。先说清楚39题是元素可重复选取但因为原始数组无重复所以结果天然不重复40题是元素只能用一次但原始数组里有重复如果朴素回溯会产生重复的组合。举个例子candidates [1, 1, 2, 5, 6, 7, 10]target 8。朴素回溯会同时找到[1, 1, 6]和[1, 2, 5]但如果第一个1和第二个1被分别作为“开头”可能会出现两个[1, 7]一个用了第一个1一个用了第二个1。这就是“结果重复”——两个组合内容完全一样只是在数组中选取的下标不同。所以40题的核心不是“限制元素使用次数”这只要递归传i1就解决了而是“如何把值相同但下标不同的选取方式合并成一种”。这才是去重问题的真正难点。2.2 排序used数组去重的标准姿势去重有一个公认的解法先排序然后引入一个used布尔数组标记某个元素在当前递归路径上是否已被使用。代码长这样class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint candidates, int target, int startIndex, vectorbool used) { if (target 0) { result.push_back(path); return; } for (int i startIndex; i candidates.size(); i) { if (i 0 candidates[i] candidates[i-1] !used[i-1]) continue; if (target - candidates[i] 0) break; used[i] true; path.push_back(candidates[i]); backtracking(candidates, target - candidates[i], i 1, used); path.pop_back(); used[i] false; } } public: vectorvectorint combinationSum2(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); vectorbool used(candidates.size(), false); backtracking(candidates, target, 0, used); return result; } };去重的关键就一行if (i 0 candidates[i] candidates[i-1] !used[i-1]) continue;这行代码的判定逻辑要从两个维度看。第一个维度是for循环的横向遍历它相当于在同一棵树的同一层上尝试不同的元素第二个维度是递归的纵向深入相当于在一条树枝上逐层叠加选择。去重要去除的是“同一层重复”因为同一层选了值相同的元素会产生重复的组合分支而同一条树枝上允许出现重复值比如[1, 1, 6]里两个1是不同下标的同值元素它们在一条分支上必须被保留。!used[i-1]判断的就是前一个相同的元素是否“没在当前树枝上被用过”。如果没用过说明前一个相同值是在同层被跳过的或已经作为另一个分支处理完了那当前这个值就会产生与之前完全相同的组合应当跳过。很多博客会提到一个让人疑惑的点为什么这里的判断写成!used[i-1]而不是used[i-1]其实两者在组合类的去重里都可能通过但含义完全不同。!used[i-1]是“同层去重”的标准写法而used[i-1]表达的是另一种思路——当前元素与上一个相同元素在同一树枝上说明当前是在递归深入过程中又取了一个同值元素这在限制每个元素只能用一次时是非法状态也应该跳过。两种写法在不同题目里各有适用范围我建议先把!used[i-1]吃透这是回溯去重的正统姿势搞清楚它之后后面学排列问题时会少很多混乱。2.3 只靠startIndex也能去重另一种写法的本质很多解答没有用used数组也通过了。核心只有一行if (i startIndex candidates[i] candidates[i-1]) continue;这个写法理解起来其实更直观在每一层for循环中i等于startIndex时是这一层的第一个元素不需要去重只有当i大于startIndex且当前元素和上一个元素值相同才说明同层出现了重复选择。对比一下两种写法的本质i startIndex等价于i 0 !used[i-1]吗在组合类问题里几乎等价。因为递归每次都从i1开始backtracking传进去的startIndex天然保证了同一树枝上不会再次选取同一个下标的元素。也就是说当i startIndex时前一个元素一定不是当前路径上的元素它要么是上一层已处理完的分支起点要么是同层已经遍历过的元素此时遇到同值元素必定是同层重复。所以我的建议是used数组法通用性更强因为后面遇到排列问题时元素不能再从i1开始取需要从头遍历整个数组那时used数组是必须的。但如果你只是在做组合类题目理解i startIndex这种去重法可以少写不少代码思路也更干净。刷题阶段不要两种都背选一种练熟再去理解另一种的差别。3. 分割回文串把“切字符串”翻译成“选组合”3.1 为什么分割问题能套回溯切割线就是组合里的元素131题要求把字符串s分割成若干子串使得每个子串都是回文串返回所有可能的分割方案。第一次看到这个题的人大概率想的是如何暴力枚举所有切割位置。字符串长度为n切割位置一共有n-1个每个位置切或不切就是2的n-1次方种方案——这就是回溯的搜索空间。关键认知在于切割一个字符串本质上就是在n-1个间隙中选k个位置下刀。选位置就是组合问题k不固定就是回溯问题。把“切割线”当成组合题里的“被选取元素”把“一个完整的切割方案”当成“一个组合”逻辑就通了。代码实现class Solution { private: vectorvectorstring result; vectorstring path; bool isPalindrome(const string s, int start, int end) { while (start end) { if (s[start] ! s[end]) return false; start; end--; } return true; } void backtracking(const string s, int startIndex) { if (startIndex s.size()) { result.push_back(path); return; } for (int i startIndex; i s.size(); i) { if (isPalindrome(s, startIndex, i)) { path.push_back(s.substr(startIndex, i - startIndex 1)); backtracking(s, i 1); path.pop_back(); } } } public: vectorvectorstring partition(string s) { backtracking(s, 0); return result; } };这里startIndex的含义发生了变化在组合题里它是“从数组的哪个下标开始选择”在分割题里它是“从字符串的哪个位置开始切下一刀”。for循环里的i就是当前这一刀切到的位置区间[startIndex, i]就是当前分割出来的第一个子串。如果这个子串是回文就把它加入path然后从i1继续切割剩余部分如果不是回文直接跳过这个i继续往后扩大切割范围。递归终止条件也更直观startIndex走到字符串末尾说明整条字符串都切割完毕当前path里的方案就是一个合法分割。比如s aab搜索过程会先试切a | ab然后试切aa | b最后试切aab但aab不是回文所以被剪掉。结果就是[[a,a,b],[aa,b]]。3.2 回文判断的两个优化方向上面代码里每次递归都要调用isPalindrome函数用双指针扫一遍区间判断是否是回文。在小数据量下没问题但字符串一长这个判断会在回溯中被反复执行时间复杂度会被拖高。第一个优化方向是提前预处理用动态规划把任意区间[i, j]是否是回文的结果存下来后面判断时直接查表O(1)搞定。递推关系很明确如果s[i] s[j]且i1到j-1也是回文或者区间长度小于等于2那么i到j就是回文。vectorvectorbool isPal(s.size(), vectorbool(s.size(), false)); for (int i s.size() - 1; i 0; i--) { for (int j i; j s.size(); j) { if (s[i] s[j]) { if (j - i 1) isPal[i][j] true; else isPal[i][j] isPal[i1][j-1]; } } }这里有个容易写错的点dp数组的遍历顺序。因为isPal[i][j]依赖isPal[i1][j-1]也就是左下方i增大、j减小的格子所以i必须从大到小遍历j从小到大遍历。如果i从0开始正序遍历计算isPal[i][j]时isPal[i1][j-1]还没被填出来结果就错了。第二个优化方向是减少substr的拷贝开销。很多初学者在for循环里先截子串再判断回文例如先string str s.substr(startIndex, i - startIndex 1);再调用isPalindrome(str)。这个做法在回文判断失败时会白白做一次子串拷贝。标准做法是先做回文判断通过之后才截取子串加入path一次无效拷贝都不做。3.3 131题调试中容易翻车的点这个题看起来是三个题里代码最短的但实际调试时翻车点不少。第一个翻车点是直接拿原始字符串去截却不注意区间边界。substr的第二个参数是长度不是结束下标。写成s.substr(startIndex, i)会把结束位置搞错应该写成s.substr(startIndex, i - startIndex 1)。这个细节我见过不止一个人踩坑。第二个翻车点是终止条件写成if (startIndex s.size() - 1)。如果最后一个字符单独作为一个回文子串被切出来startIndex确实会走到s.size()而不是s.size() - 1。写成等于size() - 1会导致最后一种分割方案丢失而且很难察觉因为结果只少了一个case。第三个翻车点是在判断回文时把参数写反比如调用isPalindrome(s, i, startIndex)。这个错误很隐蔽因为有些用例恰好字符串对称什么结果都看不出来但换一个不对称的用例立刻出问题。写这类题的时候参数的起始和结束下标一定要保持统一顺序我的习惯是统一写成[start, end]闭区间避免胡思乱想。4. 三道题放在一起回溯阶段最容易混淆的细节总结4.1 回溯模板与三题的参数差异对照刷到第23天回溯题已经接触了不少但大多数时候我们不是不会写模板而是不知道该在哪一步调整模板。我把三道题的差异整理成一张表方便对照对比维度组合总和39组合总和II40分割回文串131元素可否重复使用可以不可以不涉及字符串按序切分原始数据有无重复无重复有重复字符本身可能重复去重操作不需要排序同层去重回文判断就是约束递归时下标推进传入startIndex不1传入startIndex1传入startIndex1剪枝方式排序sum溢出break排序sum溢出break去重回文判断失败跳过终止条件sum targettarget 0startIndex s.size()这张表值得反复看。第4行“递归时下标推进”是最容易出错的39题允许重复选所以递归参数保持i保证下一层还能选当前位置40题不允许重复选所以递归参数是i1131题每一刀切完下一刀只能从当前位置后面切所以也是i1。想明白这一行的逻辑回溯的“选择空间”这一概念就通了。4.2 关于used数组、startIndex、排序——什么时候用哪个刷过几道回溯题之后很多人会陷入“不知道该上什么去重手段”的纠结。我提供一个简单的判断顺序第一步看原数组有没有重复元素。没有重复不用专门去重比如39题。有重复但要求结果不重复比如40题才需要去重。第二步看元素能否重复使用。能重复用递归传i不能用递归传i1。这是两个完全独立的维度别混在一起。40题是“原数组有重复元素不能重复用”所以既要去重又要传i1。第三步决定去重怎么做。如果已经排序用i startIndex candidates[i] candidates[i-1]最简单如果需要为后面排列题打基础就顺便把used数组练熟。排序的作用要额外强调它不只是为了break剪枝更是为了让相同元素相邻这样去重时只要比较相邻元素就能识别出同值。如果40题不排序相同值散落在数组各处用相邻比较法根本去不干净用used数组也要处理更复杂的情况。所以40题排序是前置条件不是可选项。4.3 刷题之外的收获从“套模板”到“理解树枝和树层”三道题刷下来我觉得最有价值的不是记住每一题的写法而是建立起“树层”和“树枝”这两个概念。回溯搜索的过程是在一棵树上DFS。树的每一层代表for循环的一次横向扩展每一条路径代表递归的纵向深入。同一个元素值在同层再次出现生成的是重复分支必须去重同一个元素值在树枝上再次出现可能恰恰是合法组合的一部分必须保留。这就是“树层去重”和“树枝去重”的根本区别。这个理解在后面做排列问题时还会再次派上用场。排列问题中同一树枝上不允许重复使用同一个下标但不同下标的同值元素可以出现在同一路径上这时配合used数组就能写对。我今天刷这三道题时用了一个很土但很有效的调试方法在backtracking函数入口打印path和startIndex能直观看到每一步选择了什么、递归从哪里进入下一层。遇到结果不对的情况先看打印的搜索路径比反复读代码找bug快得多。另一个小技巧是做题时统一用target递减的写法。39题里我用sum累加40题里我用target递减刷完发现递减写法在剪枝判断上更顺手——target - candidates[i] 0直接break不需要额外维护一个sum变量。刷题的时候保持一致性能减少很多认知负担。这三题做完回溯的“组合类”问题基本就掌握七八成了。接下来如果继续往后推进到排列、子集、棋盘问题你会发现大部分思考方式是一样的先画一棵树再想清楚每一层选什么、每一层从哪里开始选、什么条件能终止、什么条件能剪枝。把今天这三道题里反复纠结的细节想透后面会顺很多。