企业官网建设流程全解析

1. 回溯算法三连击：从子序列到全排列的层层递进

打卡第25天，回溯专题终于进入“排列类”题目的环节。前面我刷过组合、分割、子集，今天遇到的这三道题，基本概括了回溯算法在“排列”场景下的全部常见考法：491递增子序列看的是“约束条件下的子集枚举”，46全排列看的是“最标准的有序排列模板”，47全排列II看的则是“去重逻辑和剪枝时机”。

如果你同时刷过组合总和II和子集II，你会明显感觉到今天这三题里的去重思路和之前的树层去重一脉相承，但同时又各自多了一个陷阱。很多同学做到第47题时会发现：明明思路看着和40题组合总和II差不多，怎么一写就错？这就是因为排列和组合在最底层的“选数逻辑”上完全不同——组合用的是startIndex来约束剩余可选元素，而排列需要每一层都从头扫描、配合used数组标记已选元素。这个差异理解透了，回溯题才算真正入门。

今天这篇文章我把自己刷这三道题时走过的弯路、对比过的解法和总结出来的速记口诀都整理一遍，特别适合正在跟训练营的伙伴、以及刷了一部分回溯题但总在去重和边界条件上卡壳的同学阅读。

开始之前，先把三题的定位列清楚，后面每一道我单独拆开细讲：

• 491 递增子序列：子集框架 + 同一层去重（但不能排序）
• 46 全排列：排列框架 + used数组标记，无重复元素
• 47 全排列II：排列框架 + used数组标记，有重复元素，所以既要树枝去重又要树层去重

三题互为递进，建议按顺序刷完。

2. 491.递增子序列：不能排序的时候，怎么去重？

2.1 题目到底在问什么

给定一个整数数组nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。

举个例子，nums = [4, 6, 7, 7]，输出结果里不能包含两个一模一样的[4, 7]，同时子序列必须保持原数组的相对顺序，不能重排。

第一次看到这个题，很多人（包括我）的第一反应是：这不就是子集问题吗？按照回溯老套路，先把数组排序，然后在同一层判断nums[i] == nums[i-1]就跳过，再在收集结果时判断一下是否递增，完事。

我也确实是这么写的，但跑了一遍用例之后直接发现问题——这题不能排序。

因为子序列要求保住原有相对位置，比如[4, 6, 7, 7]排序后变成[4, 6, 7, 7]看似一致，但如果来一个[4, 7, 6, 7]，排序后就变成[4, 6, 7, 7]，原来不存在[4, 6]这个子序列，排序之后竟然出现了。排序破坏了原数组的顺序信息，子序列对顺序的敏感性决定了这条路走不通。

2.2 同一层去重的正确姿势：set

既然不能排序，那传统nums[i] == nums[i-1]的写法就失效了。我们需要一种不依赖排序的去重手段。

很多教程直接给出答案：在每一层的递归中定义一个unordered_set<int>，当遍历某一层的候选元素时，如果这个元素已经被本层用过，就跳过。这样，在同一递归深度不可能出现两个相同的选择分支。

为什么用 set 就能解决？因为去重的本质是“同一个位置不能选重复的值”。排序法是通过相邻元素比较来实现这点，set 则是靠哈希记录历史选择来实现，两者不冲突，只是应用场景不同。

这里有个非常重要的细节：unordered_set必须定义在每一层递归内部，而不是全局变量。它只保证“树的同一层”不选重复元素，而不同层之间完全可以选相同的值。放在函数内层，递归到下一层就自动创建新的 set，天然实现层间隔离，不需要手动清理。

补充一句：这里也可以用一个局部bool used[201]数组替代，因为本题数值范围是 -100 到 100，做个偏移即可，速度比 set 更快，代码也不复杂。但训练营教程标准答案用 set，先用 set 把逻辑理清楚，进阶时再用数组优化。

2.3 递增判定和剪枝条件

收集结果时，要求当前路径path中至少有两个元素，并且最后一个元素大于等于path的最后一个元素，才允许加入path。

换句话说，在递归入口，除了“先判断当前 path 是否满足条件并收集”之外，进入横向遍历时，对每个候选元素还要做一次递增判定：

• 如果nums[i] < path.back()（不满足递增），直接跳过；
• 如果nums[i]在本层 set 中已经出现过，直接跳过。

这样纵向递归和横向遍历双重约束下，每一层的选择都会被严格过滤。

有个小细节值得注意：递增子序列题目里“递增”定义为非递减，也就是允许[1, 2, 2]这种带相等元素的子序列。判断时要注意用<而不是<=，写反了会漏掉相等值的合法组合。我第一版就用<=跳过导致[1, 2, 2]没被收集，查了半天才发现是边界写错。

2.4 C++参考实现与复杂度

class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { if (path.size() > 1) { result.push_back(path); } unordered_set<int> used; for (int i = startIndex; i < nums.size(); i++) { if (!path.empty() && nums[i] < path.back()) { continue; } if (used.find(nums[i]) != used.end()) { continue; } used.insert(nums[i]); path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } } public: vector<vector<int>> findSubsequences(vector<int>& nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };

时间复杂度方面，每个元素在每一层都有选与不选两个分支，最坏情况是 O(2^n * n)（n 是数组长度，path 复制到 result 需要 O(n)）。空间复杂度是递归栈深度 O(n)。

实操中我建议调试时打印每一层的path和used，能直观看到 set 是层间隔离的。

2.5 一个实际踩过的坑：set 定义在哪一层

刚刷这题时，我把unordered_set<int> used定义成了类的成员变量，结果跑出来大量重复结果。原因很简单：回溯递归会回到上一层，如果 used 是全局的，之前层的选择记录会“残留”到当前层，导致相同值被误判为重复而剪掉，结果漏解、重复解并存。

这个问题不看 debug 输出真的很难发现。后来我随手在递归入口打印 set 的 size，才意识到每层都应该从零开始。这个错误特别隐蔽，建议刷题时遇到“结果集莫名少了一些分支”的情况，优先检查这类“看似局部实则全局”的变量。

3. 46.全排列：为什么排列必须用used数组

3.1 排列和组合的底层差异

先看题目要求：给定一个没有重复数字的序列nums，返回其所有可能的全排列。

[1, 2, 3]的输出中，[1, 2, 3]和[2, 1, 3]是两种不同的排列。而在组合类问题里（例如求三数组合），[1, 2, 3]和[2, 1, 3]会被视为同一个组合，因此只保留一个。

这个本质区别直接决定了回溯逻辑：

• 组合问题用startIndex控制遍历起点，第 i 层从 i+1 开始选，天然保证“后面的元素只在后面选”，从而避免乱序组合重复；
• 排列问题中每个位置都可以选数组中的任意元素，所以递归每层必须从i = 0开始遍历，但要用一个used数组（或布尔数组）记录“当前路径已经选了哪些下标”，同一路径内避免重复选同一个元素。

通俗点说：排列就像往一排格子里填数字，每个格子都可以从全部数字里选，但填过数字的格子不能再填；组合则是从队伍里挑人，挑完一个只能往后继续挑，不会再回头。

3.2 递归终止条件和收集时机

排列的终止条件非常直观：当path.size() == nums.size()时，所有数字都用完了，把path加入结果，返回。

这个写起来很简单，但初学者容易忽略一点：因为排列的每一层遍历范围都是整个数组，如果不用used做标记，递归时会无限递归，如先选1，再选1，再选1……直到栈溢出。

所以used数组的两重作用必须理解清楚：

• 纵向约束：进入下一层时，标记为 true 的下标不可再选，保证一个数字不会在同一路径中重复出现；
• 撤销逻辑：递归返回后，把used[i]改回 false，让同一层的下一个分支可以重新选择该数字。

这里和组合类问题的startIndex恰好形成对照：组合靠 startIndex 隔离“前面的元素”，排列靠 used 隔离“路径中已选元素”。

3.3 标准解法与优化点

class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, vector<bool>& used) { if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } public: vector<vector<int>> permute(vector<int>& nums) { result.clear(); path.clear(); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };

一个可行的优化是：当提前知道某分支不可能产生有效排列时直接跳过。但本题没有重复元素，也没有额外约束，所以无需剪枝。排列类题目中剪枝通常在“有重复元素 + 要求去重”的47题中出现，也就是下一道题的核心。

这里我还想多提一句“为什么全排列的复杂度是 O(n!·n)”。因为排列数量本身就有 n! 种，每种排列复制进结果需要 O(n) 时间。很多新手纠结回溯过程为什么这么慢，其实在 n 不大时没问题；一旦 n 到 10 以上，n! 就会暴涨到 3628800，配合复制开销已经很难跑完，更别说 n 到 15。所以回溯类题目通常 n 都很小，看到大范围数据基本可以判断题目另有思路。

3.4 从组合模板切到排列模板的思维转换

刷题过程中我总结了一句口诀：“组合用 startIndex，排列用 used；组合收集叶子，排列也收集叶子，但排列的叶子就是满了的 path。”

这句话帮我少走了很多弯路。在46题之前，我连续刷了组合总和、分割、子集，模板非常固化。结果第一次写全排列时，自然而然地写了startIndex，然后发现输出只有[1,2,3]一种排列。这不是编码问题，是思路没转过来：组合里 startIndex 是为了防重复组合，排列里需要的是“每个位置都能回头选”。

另外，排列不需要先排序，因为无重复元素时排序除了增加开销，对结果没有影响。只有当题目出现“重复元素且结果去重”时排序才会作为去重的辅助手段登场。

4. 47.全排列II：排序+used才是去重黄金搭档

4.1 有重复元素之后，问题立刻变得复杂

题目描述：给定一个可能包含重复数字的序列nums，返回所有不重复的全排列。

对比46题，唯一变化是数组里可能有重复数字。比如nums = [1, 1, 2]，标准排列是 6 种，但[1a, 1b, 2]和[1b, 1a, 2]在数值上都是[1, 1, 2]，必须去重。

去重的难点在于：我们不能简单地“遇到相同的数就跳过”，因为不同位置上的相同数字可能在同一个排列中同时出现（一个排列里必须包含两个1）。真正要去重的是“在树的同一层横向扩展时，不重复选择值相同的元素”。

这句话怎么理解？递归树的每一层代表“当前这个位置放哪个数字”。如果nums[0]和nums[1]都是 1，那么它们放在同一个位置上产生的排列是一样的，比如第0位放nums[0]=1和第0位放nums[1]=1，后续路径完全相同，结果必然重复。所以同一层必须二选一，只放一次。

但纵向递归到下一层时，如果第一个1已经在 path 中，那么第二个1完全可以选择，因为两者在同一个排列里的不同位置，此时结果是合法且不重复的。这就是“树层去重”和“树枝去重”的经典区分。

4.2 排序到底为了方便什么

排序的核心目的：让重复元素相邻。重复元素相邻后，在一层遍历时只需检查“当前值是否和前一个值相同”，并且“前一个值是否已经被使用过（通过 used[i-1] 判断）”，就可以决定是否跳过当前元素。

这里的判断条件大家在网上会看到两种写法：

if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue; // 写法A if (i > 0 && nums[i] == nums[i-1] && used[i-1] == true) continue; // 写法B

两种写法都能通过，但语义上有微妙差别。

对于写法A，used[i-1] == false表示同一层的横向去重：因为上一个相同元素在横向遍历中已被选择过并回溯撤销，所以 used[i-1] 为 false，此时如果再选当前元素，就会和上一个分支产生重复。

对于写法B，used[i-1] == true表示树枝上的绝对去重：前一个相同元素已经出现在当前路径上，那当前元素就不能再选，这其实是在纵向维度上禁止了重复值的“连续使用”。

那么到底哪种写法更正确、更符合训练营的主流思路？用“层”的视角分析最清晰：

回溯到同一层时，used[i-1]应该是 false（因为递归返回时已经把标记撤销了），此时用写法A判断used[i-1] == false是合理的剪枝；而递归到下一层时，used[i-1]可能是 true（因为上一层的相同值仍在该层的 path 中），但此时我们不希望去重——下一层本来就应该允许选第二个1。

那为什么两种写法都能通过？因为写法B虽然逻辑上是在做树枝去重，但放到本题数据条件下，遇到used[i-1] == true的场景恰好出现在树层去重需要剪枝的节点附近，结果碰巧也能得到正确答案。

实操建议：训练营和相关题解统一使用写法A，也就是used[i-1] == false时跳过。理由很简单，当上一个相同元素没有被使用（说明是同层），这个才是真正的横向重复；如果上一个元素被使用了（说明是在路径上），当前元素恰好可以选，不应该被剪掉。

4.3 两个版本的完整代码

先看写法A（推荐参考的版本）：

class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, vector<bool>& used) { if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { // 树层去重：同一层相同元素只取第一个分支 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } // 树枝去重：同一个排列中不能重复用同一个下标的元素 if (used[i] == true) { continue; } used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { result.clear(); path.clear(); sort(nums.begin(), nums.end()); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };

再看不排序的写法：用每层新建 set 也能去重，但排序+used整体性能更好，且思路更统一，下面这种 set 写法用来辅助理解可以，不建议作为主写法：

// 不排序的版本：每次递归新建 unordered_set 记录本层已取过的值 class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, vector<bool>& used) { if (path.size() == nums.size()) { result.push_back(path); return; } unordered_set<int> layerUsed; for (int i = 0; i < nums.size(); i++) { if (used[i] || layerUsed.count(nums[i])) continue; layerUsed.insert(nums[i]); used[i] = true; path.push_back(nums[i]); backtracking(nums, used); used[i] = false; path.pop_back(); } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { result.clear(); path.clear(); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };

结论：排序 + used[i-1] == false 是回溯去重的最稳方案，推荐记忆这套写法，因为组合总和II、子集II也都通用。

4.4 去重维度对比：为什么同一层去重不等于全局去重

很多新手会把“同一层去重”误以为“只要值相等就跳过”。为了说清这一点，我们再拿[1, 1, 2]举例：

• 第一层（第0位）选第一个1。进入下一层，第1位不能选第一个1（已经 used），但可以选第二个1。此时 path = [1, 1]，这是合法的排列前缀。
• 第一层选第二个1时，由于nums[0] == nums[1]且used[0] == false（第一个1已被回溯撤销），按照写法A直接跳过。这样第一层永远不会产生“第0位放第二个1”的重复分支。

如果错误地写成used[i-1] == true时跳过，在第一层选第二个1的场景下，used[0]是 false，所以不跳过，会产生一个与“第0位放第一个1”完全重复的分支，结果中就会出现两个相同的[1,1,2]。只有在特定递归时机下巧合弥补，才让写法B免于出错。

这一步的“为什么”吃透了，去重就不再是玄学。

4.5 三道题放在一起看：模板对照表

为了便于复习，我把三题的模板参数整理如下：

这张表在我复盘时非常有用。特别是“是否排序”这一列，491是绝对不能排序，47是必须排序，同样是去重，两者在排序上的态度完全相反，搞混了题目就废了。

5. 实战调试心得：这些坑我全踩过一遍

5.1 忘记撤销 used 标记导致结果莫名爆炸

46和47题里最容易犯的低级错误是：递归前used[i] = true，递归后忘记used[i] = false。

表象：结果中途正常，后面出现大量重复或缺失排列，程序甚至可能栈溢出。

排查建议：在每次递归调用前后打印path和used数组。如果发现某个分支结束后进入另一个分支时 used 还是全 true，基本就是撤销写漏了。回溯算法的核心心法就是“递归前做选择，递归后撤销选择”，这两个操作是一对，要写在一起。

5.2 491题里把 used 做成全局变量

之前已经说过，这题每层的 set 必须局部创建。我还想强调一个记忆技巧：所谓“同一层去重”，其实每次横向循环中收集的是“本层已尝试过的值”，该层循环结束这个 set 就没有存在意义了，所以放在函数体内部天然合理。当成全局变量用，虽然单靠局部清理也能实现，但多一个清理步骤就多一个出错点。

5.3 排列题里错误使用 startIndex

在这三题之前，我连续刷的都是组合类，手指条件反射般写成：

backtracking(nums, i + 1, used);

这在46题里会漏掉大量排列。例如[1,2,3]，第一层选了1，第二层从2开始选，就永远不会出现[1,3,2]。全排列的本质是“每一层都可以回头选以前没选过的数”，所以只能用used判断，而不是用 i+1 限制。

有一个过渡技巧：如果你实在分不清该用哪个，先问自己“如果这一步选了某个数，下一步还能不能选排在它前面的数？”能，就用 used；不能，就用 startIndex。

5.4 491题递增判断写错边界

再补充一个细节：有些题解在递归开头写：

if (path.size() > 1 && path.back() >= nums[i])

这是把递增判断混进横向循环里的写法，思路一样，但注意nums[i]是在path非空时与path.back()比。推荐在 for 循环开头就写上：

if (!path.empty() && nums[i] < path.back()) continue;

这是习惯问题，但至少可以减少一次无效递归。

5.5 关于剪枝的定位思考

回溯的剪枝有两种：横向剪枝（同一层跳过某些元素）和纵向剪枝（提前终止不可能的分支）。

491题的递增判断属于横向剪枝，47题的used[i-1] == false属于横向剪枝，而used[i] == true本质上是纵向约束，防止同一路径重复选同一元素。

分清这两类剪枝，阅读别人代码时会快很多，自己写时也不容易混淆去重条件。

6. 训练营打卡节奏的一点个人体会

从第20天左右开始，回溯算法的题型密度明显加大，组合、分割、子集、排列四类问题一个接一个。如果你跟我一样是边工作边刷题，很容易在某一天产生“今天题目做出来了，但脑子一片空白”的错觉。

到了第25天这个节点，我的建议是放慢一天，专门做一个横向总结：把组合总和II、子集II、递增子序列、全排列II拉出来对比一次。很快就能发现，刷题到最后其实就是在比对“去重条件”和“遍历起点”。

正式因为这样，我在写这篇打卡总结时，把三题的模板差异放在最前面讲，把每一题的“为什么这么做”放在代码前面。如果只是把代码抄一遍，下一次遇到变种题照样不会，那打卡就失去意义了。

今天之后，回溯算法还剩棋盘类问题（N皇后、解数独）没刷，这两类题会从一维递归升级到二维递归，但核心依然是“选择 + 撤销选择”的循环。基础打牢之后，那个坎不会太难。

更细节的做题感受是：最近几天我用“模板速写”的方式练题，看到题目先不急着写代码，在草稿纸上回答三个问题——第一，这题属于组合/分割/子集/排列中的哪一类？第二，需不需要排序？第三，去重放在哪一层？三个问题回答完，代码基本就是套模板的事。这个流程推荐给大家试试。

最后再分享一个小技巧：46题的全排列使用迭代写法其实有现成的next_permutation函数可以直接调，刷题阶段尤其训练营里不建议依赖库函数。自己手写一遍回溯全排列，才能真正理解递归状态切换的过程。等彻底掌握回溯，之后的性能优化才有基础。

打卡第25天结束，明天继续棋盘问题的魔鬼训练。