大家好我是程序员无隅第一次写回溯时我们很容易把注意力放在append()、递归调用和pop()上最后记住了一段模板却不知道为什么递归参数是i也不知道下一层为什么传i 1或j 1。其实写回溯最重要的并不是先背模板而是先把递归函数的含义说清楚。只要能回答“当前做什么、当前还要解决什么、做完以后还剩什么”这三个问题代码通常只是把这条逻辑翻译出来。本文从 LeetCode 78「子集」出发分别使用“选或不选”和“枚举选哪个”两种写法理解回溯最后再把同样的分析方法迁移到 LeetCode 131「分割回文串」。一、为什么写回溯前要先回答“三问”假设我们正在逐位构造一个字符串path[i]表示答案的第i个位置。这时可以先回答当前操作是什么枚举一个合法字母填入path[i]。dfs(i)解决什么子问题在前i个位置已经确定的基础上从第i位开始继续构造字符串。做完选择后下一个子问题是什么第i位已经填好调用dfs(i 1)继续构造第i 1位及后面的部分。这三问分别对应回溯代码里的三件事forchinchoices:# 枚举当前选择path.append(ch)# 执行当前选择dfs(i1)# 解决下一个子问题path.pop()# 撤销当前选择这里真正决定递归写法的不是append()和pop()而是我们对dfs(i)的定义。如果把dfs(i)定义成“处理第i个输入元素”下一层通常是dfs(i 1)如果把它定义成“从下标i开始枚举下一个要选的元素”那么选择nums[j]后下一层就应该是dfs(j 1)。递归参数不是凭感觉传递的它必须与递归函数的语义保持一致。二、回溯算法的本质在决策树上构造答案回溯可以理解为在一棵决策树上进行深度优先搜索。树上的一个节点表示当前已经完成了一部分选择。从一个节点走向子节点表示做出一次新选择。到达满足条件的节点时把当前路径收集为答案。返回父节点前撤销刚才的选择再尝试其他分支。因此写回溯时需要先确定两个核心对象。1.path已经完成了哪些选择path保存从根节点走到当前节点的选择结果。例如在子集问题中path [1, 3]表示当前已经选择了数字1和3。它不是“接下来还要做什么”而是已经做完的选择所形成的局部答案。2.dfs(状态)接下来还要解决什么问题递归参数描述剩余问题。例如dfs(i)可以定义为在当前path的基础上从下标i开始继续构造后面的答案。于是一次标准回溯过程就是path.append(choice)# 做选择dfs(next_state)# 解决选择之后的剩余问题path.pop()# 恢复到选择之前的状态pop()并不是为了“删除错误答案”。它的作用是恢复现场让同一个path可以继续表示父节点的状态随后尝试另一种选择。因此回溯的核心链路可以概括为当前状态 → 枚举一个合法选择 → 修改 path → 进入下一个状态 → 恢复 path。三、LeetCode 78用两种视角生成所有子集给定一个不含重复元素的整数数组nums返回它的所有子集。以nums [1, 2, 3]为例答案包括[] [1] [2] [3] [1,2] [1,3] [2,3] [1,2,3]这道题有两种经典回溯写法。它们没有改变问题本身只是观察决策树的角度不同。3.1 方法一站在输入角度选或不选站在输入数组的角度我们依次询问每个元素nums[i]要不要进入当前子集每个元素只有两种状态不选nums[i]选择nums[i]回溯三问当前操作是什么决定nums[i]选还是不选。当前子问题是什么dfs(i)表示在前i个元素已经决定完的基础上继续决定下标i及后面的元素。下一个子问题是什么无论是否选择nums[i]它都已经被处理完所以下一层都是dfs(i 1)。代码defsubsets(nums):ans[]path[]nlen(nums)defdfs(i):ifin:ans.append(path.copy())return# 不选 nums[i]dfs(i1)# 选择 nums[i]path.append(nums[i])dfs(i1)path.pop()dfs(0)returnans这棵搜索树一共有n层每一层处理一个输入元素。只有到达i n时才说明所有元素的“选或不选”都已经决定完因此在叶子节点收集答案。这里的path.copy()不能省略。path在整个搜索过程中会不断修改如果直接保存path答案数组中的多个位置将引用同一个列表后续回溯会一起改变它们。3.2 方法二站在答案角度枚举下一个选谁换一个角度不再逐个询问输入元素而是直接考虑当前要往path里放哪个数如果当前允许从下标i开始选择那么可以枚举j i, i 1, ..., n - 1把nums[j]作为答案中的下一个元素。回溯三问当前操作是什么从当前允许选择的范围[i, n)中枚举一个下标j把nums[j]加入path。当前子问题是什么dfs(i)表示在当前已经选好若干数字的基础上从下标i开始继续枚举下一个要选择的数字。下一个子问题是什么如果选择了nums[j]下一次只能从j 1开始继续选择因此调用dfs(j 1)。代码defsubsets(nums):ans[]path[]nlen(nums)defdfs(i):# 当前 path 本身就是一个合法子集ans.append(path.copy())forjinrange(i,n):path.append(nums[j])dfs(j1)path.pop()dfs(0)returnans注意这里的下一层是dfs(j 1)不是dfs(i 1)。因为i只表示本层允许选择的起始位置真正被选中的是nums[j]。选择完成后需要越过下标j下一层才能保证下标严格递增。3.3 为什么不会遗漏也不会产生重复子集假设某个子集选中的下标是i₁ i₂ i₃第二种写法会依次选择i₁ → i₂ → i₃任何一个子集都能把元素按照原数组下标从小到大排列因此它一定对应搜索树中的一条路径。这说明不会遗漏。同时递归只允许从当前下标之后继续选择所以下标不能回头。[1, 3]只能通过“先选择1再选择3”得到不可能再通过“先选择3再选择1”生成一次。这说明不会重复。递增下标同时建立了完整性和唯一性每个子集都对应唯一的一条递增下标序列。3.4 两种方法到底有什么区别第一种方法站在输入角度当前元素选不选它的递归深度固定为n每个叶子节点对应一种完整的选或不选方案。第二种方法站在答案角度当前答案的下一个元素选谁它的答案长度不固定每进入一个递归节点当前path就已经代表一个合法子集因此可以立即收集。两种写法都会生成2^n个子集。复制每个子集还需要与其长度成正比因此时间复杂度O(n × 2^n)递归栈与路径空间O(n)如果计算返回结果本身占用的空间O(n × 2^n)四、从子集迁移到 LeetCode 131 分割回文串LeetCode 131 要求把字符串分割成若干个回文子串并返回所有合法分割方案。例如s aab合法答案为[a, a, b] [aa, b]这道题与子集很像字符串中的切割位置同样可以看成一系列选择。它也有两种观察角度。4.1 方法一判断当前位置切不切站在输入位置的角度依次判断每个字符后面是否切一刀。回溯三问当前操作是什么判断位置i后面是否切割。不切当前子串继续向后延长。切取出s[start:i 1]只有它是回文串才能加入path。当前子问题是什么dfs(i, start)表示当前正在检查位置i未完成子串从start开始继续决定后面的切割方式。下一个子问题是什么不切时当前子串起点不变进入dfs(i 1, start)。切割时下一段从i 1开始进入dfs(i 1, i 1)。defpartition(s):ans[]path[]nlen(s)defis_palindrome(left,right):whileleftright:ifs[left]!s[right]:returnFalseleft1right-1returnTruedefdfs(i,start):ifin:ifstartn:ans.append(path.copy())return# 当前位置后面不切继续延长当前子串ifin-1:dfs(i1,start)# 当前位置后面切一刀ifis_palindrome(start,i):path.append(s[start:i1])dfs(i1,i1)path.pop()dfs(0,0)returnans一句话记忆依次判断每个字符后面切不切切出来的部分必须是回文串。4.2 方法二枚举下一段在哪里结束站在答案的角度我们不再判断每个位置“切不切”而是直接枚举下一段回文串的结束位置。回溯三问当前操作是什么从尚未分割的第一个字符i开始枚举结束位置j。如果s[i:j 1]是回文串就把它加入path。当前子问题是什么dfs(i)表示前i个字符已经分割完成从下标i开始继续分割剩余字符串。下一个子问题是什么选择s[i:j 1]后这一段已经完成下一次从j 1开始因此调用dfs(j 1)。defpartition(s):ans[]path[]nlen(s)defis_palindrome(left,right):whileleftright:ifs[left]!s[right]:returnFalseleft1right-1returnTruedefdfs(i):ifin:ans.append(path.copy())returnforjinrange(i,n):ifnotis_palindrome(i,j):continuepath.append(s[i:j1])dfs(j1)path.pop()dfs(0)returnans一句话记忆每次枚举下一段回文串选多长选完以后继续分割剩余字符串。4.3 为什么子集可以立即收集回文分割却不行在子集的“枚举选哪个”写法中即使后面还有数字没有选择当前path也已经是一个完整、合法的子集。例如nums [1, 2, 3] path [1][1]本身就是答案不需要等到所有数字都处理完因此进入dfs时就可以记录。而在回文分割中s aab path [aa]此时字符b还没有被分割[aa]只是一个半成品。只有递归位置到达n说明整个字符串都被若干回文子串覆盖当前path才是完整答案。所以答案何时加入ans不能靠背模板判断。应该先问当前 path 是否已经满足题目对一个完整答案的全部要求五、一套可复用的回溯分析方法遇到新的回溯题可以按照下面的顺序分析。第一步确定path表示什么先问自己当前已经做了哪些选择在子集问题中path是已经选中的数字在分割回文串中path是已经确定的回文子串。第二步定义dfs(状态)不要只写一个模糊的“dfs用来回溯”。需要把剩余问题说完整。例如dfs(i)在当前 path 的基础上从下标 i 开始继续枚举后面的选择。定义清楚以后递归参数如何变化通常也会随之确定。第三步回答回溯三问当前操作是什么当前子问题是什么做完选择后下一个子问题是什么如果第三问无法回答就说明递归函数的定义还不够清楚。第四步确定什么时候得到完整答案结束条件不是统一的i n收集答案的位置也不一定总在叶子节点。子集的“选或不选”写法所有元素都决定完时收集。子集的“枚举选哪个”写法每个节点的path都是合法子集进入递归就收集。分割回文串只有整个字符串都被分割完时收集。结束条件取决于题目如何定义一个完整答案而不是取决于模板长什么样。第五步枚举选择递归再恢复现场最后才把前面的分析翻译成代码defdfs(state):if当前已经构造出完整答案:ans.append(path.copy())returnforchoicein当前所有合法选择:path.append(choice)dfs(next_state)path.pop()这段代码只是一个结构提示并不是所有回溯题都要机械套用。真正需要记住的是path描述已经完成的选择dfs(状态)描述尚未解决的问题每次递归只做一个当前选择然后把剩余问题交给下一层。回到子集问题“选或不选”是在遍历输入元素每层决定一个元素的状态。“枚举选哪个”是在构造答案每层决定答案中的下一个元素。当你能准确说出自己站在哪个角度、当前做什么、下一层还剩什么时回溯就不再是一段需要死记硬背的模板而是一条可以一步步推导出来的决策链。
