企业官网建设流程全解析

大家好，我是程序员无隅

第一次写回溯时，我们很容易把注意力放在append()、递归调用和pop()上，最后记住了一段模板，却不知道为什么递归参数是i，也不知道下一层为什么传i + 1或j + 1。

其实，写回溯最重要的并不是先背模板，而是先把递归函数的含义说清楚。只要能回答“当前做什么、当前还要解决什么、做完以后还剩什么”这三个问题，代码通常只是把这条逻辑翻译出来。

本文从 LeetCode 78「子集」出发，分别使用“选或不选”和“枚举选哪个”两种写法理解回溯，最后再把同样的分析方法迁移到 LeetCode 131「分割回文串」。

一、为什么写回溯前要先回答“三问”

假设我们正在逐位构造一个字符串，path[i]表示答案的第i个位置。

这时可以先回答：

1. 当前操作是什么？
   枚举一个合法字母，填入path[i]。

2. dfs(i)解决什么子问题？
   在前i个位置已经确定的基础上，从第i位开始继续构造字符串。

3. 做完选择后，下一个子问题是什么？
   第i位已经填好，调用dfs(i + 1)，继续构造第i + 1位及后面的部分。

这三问分别对应回溯代码里的三件事：

forchinchoices:# 枚举当前选择path.append(ch)# 执行当前选择dfs(i+1)# 解决下一个子问题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=[]n=len(nums)defdfs(i):ifi==n:ans.append(path.copy())return# 不选 nums[i]dfs(i+1)# 选择 nums[i]path.append(nums[i])dfs(i+1)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=[]n=len(nums)defdfs(i):# 当前 path 本身就是一个合法子集ans.append(path.copy())forjinrange(i,n):path.append(nums[j])dfs(j+1)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=[]n=len(s)defis_palindrome(left,right):whileleft<right:ifs[left]!=s[right]:returnFalseleft+=1right-=1returnTruedefdfs(i,start):ifi==n:ifstart==n:ans.append(path.copy())return# 当前位置后面不切，继续延长当前子串ifi<n-1:dfs(i+1,start)# 当前位置后面切一刀ifis_palindrome(start,i):path.append(s[start:i+1])dfs(i+1,i+1)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=[]n=len(s)defis_palindrome(left,right):whileleft<right:ifs[left]!=s[right]:returnFalseleft+=1right-=1returnTruedefdfs(i):ifi==n:ans.append(path.copy())returnforjinrange(i,n):ifnotis_palindrome(i,j):continuepath.append(s[i:j+1])dfs(j+1)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(状态)描述尚未解决的问题；每次递归只做一个当前选择，然后把剩余问题交给下一层。

回到子集问题：

• “选或不选”是在遍历输入元素，每层决定一个元素的状态。
• “枚举选哪个”是在构造答案，每层决定答案中的下一个元素。

当你能准确说出自己站在哪个角度、当前做什么、下一层还剩什么时，回溯就不再是一段需要死记硬背的模板，而是一条可以一步步推导出来的决策链。