今天进入代码随想录算法训练营第二十四天回溯算法已经来到最考验理解深度的一批题目491.递增子序列、46.全排列、47.全排列II、51.N皇后。子序列、排列、棋盘搜索三种完全不同形态的搜索场景底层却都靠同一套递归模板支撑。这四道题如果能一次性吃透你对“状态空间”的理解会有一个明显提升。尤其491题的“不排序去重”和47题的“树层去重”是很多人在面试时栽跟头的地方。另外今天的热搜词里有个有趣的点Vue3的diff优化中用到了“最长递增子序列”这个算法思想和491题研究的子序列问题同根同源后文我会专门展开讲。无论你是刷LeetCode准备面试还是纯粹想补算法基础这篇打卡记录都能给你一套可以直接复用的解题框架和易错点清单。1. 今日题目总览与回溯算法框架1.1 四道题的内在联系先给今天四道题快速画个像题目题型核心考点建议用时491. 递增子序列子序列类回溯不排序去重、结果收集时机25分钟46. 全排列排列类回溯used数组、无startIndex15分钟47. 全排列II排列去重回溯排序后树层去重30分钟51. N皇后二维棋盘回溯棋盘建模、合法性校验45分钟为什么代码随想录会把这几道题放在同一天因为它们都在解决同一个问题在一棵递归树上做深度优先搜索搜索到满足条件的路径就收集结果搜索不下去就回退。区别只在搜索空间怎么组织——子序列的搜索空间是“当前元素之后的后缀”排列的搜索空间是“整个数组中未被使用的元素”N皇后则是一个逐行推进的二维棋盘。理解这一点刷题就不是背模板而是按题目需求调整模板的形态。1.2 回溯算法的统一模板不管是哪道题回溯代码长成这样void backtracking(参数) { if (终止条件) { 收集结果; return; } for (选择 : 本层集合) { 处理节点; backtracking(路径, 下一层参数); 撤销处理; } }关键就在“处理节点”和“撤销处理”这一对动作。你可以把递归想象成进迷宫往前走一步记录当前位置走到底或走不通就退回上一步擦掉刚才的记录再换另一个方向探索。不“撤销”的话上一个分支的状态会带脏到下一个分支整个搜索树就乱了。今天四道题本质上都是在往这个模板里填不同的“状态定义”和“去重策略”。1.3 树层去重与树枝去重的本质区别去重是今天最容易出错的地方。先厘清两个概念树枝去重一条从根到叶子的路径上不能重复使用同一个元素。典型手段是used数组递归进入前标记used[i]true回溯后恢复false。树层去重在某个节点的同一层循环里如果有多个分支的值相同只保留第一个分支后面的重复分支全部剪掉。用生活场景类比你从一盒苹果里挑水果挑完第一个再挑第二个“不能重复拿同一个苹果”是树枝层面的规则而“这层我已经用红色苹果试过了另一个红色苹果就不必再试”是树层层面的规则。491题考的是树层去重而且不能靠排序实现46题考的是树枝去重靠used数组实现47题两件事叠加在一起做51题两件事都不涉及但要处理好二维棋盘的搜索空间。把这四道题连起来看去重的全貌就出来了。2. 491.递增子序列不排序怎么去重2.1 为什么这题不能先排序很多刷过“组合总和II”的同学看到去重第一反应就是“先排序再比较相邻元素”。但491题恰恰是这套思路的例外。题目要求返回原数组中所有递增子序列注意“原数组”三个字。子序列本身就不要求连续但要求元素在原数组中的相对顺序保持不变。如果先排序整个数组的相对顺序被重排你收集到的“递增序列”很可能在原数组里根本不是一个合法的子序列。举个直观例子nums [1, 3, 2, 4]。排序后变成 [1, 2, 3, 4]如果按排序后的数组去找递增子序列可以轻松凑出 [1, 2, 3]但 [1, 2, 3] 在原数组里的顺序是 1、3、2、42在3后面所以它不是原数组的子序列。排序会直接改变子序列的定义这就是491题必须放弃“排序相邻去重”的根本原因。2.2 用每层局部set做树层去重不能排序就用集合来去重。正确做法是每层递归内新建一个unordered_set记录本层已经选过的值遇到重复就直接跳过。完整代码如下class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { if (path.size() 1) { result.push_back(path); } unordered_setint 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: vectorvectorint findSubsequences(vectorint nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };这里最反直觉的点在于set是每层新建的局部变量它只对“当前这一层”的去重负责递归进入下一层后使用的是下一层自己新建的set所以不需要在回溯时做erase。你只需要保证在同一个for循环里相同值不要被选第二次就足够避免重复的递增子序列了。很多同学问“那used数组不行吗”如果用全局used数组它会在垂直方向上保留状态导致本层判断时把“上一层用过”的值也算成“本层用过”最终严重漏解。树层去重和树枝去重必须分开实现不能混用一套状态。2.3 收集结果的位置与常见误区再注意一下这段代码的终止条件path.size() 1就立刻收集但这里没有return。因为递增子序列不是“到叶子才收”而是路径上任意长度≥2的节点都可能是合法结果。收集完当前结果还要继续向深层扩展看能不能拼出更长的子序列。两个容易踩的坑误区一试图对原数组排序再用组合题的去重套路。排序会破坏子序列的定义结果必错。误区二set定义在递归函数外部并且尝试回溯时erase。多写了erase反而容易在错误时机擦除数据不如每层新建干净利落。实际笔试时491题往往不会只考“写出来”还会追问“为什么不能用排序去重”。能讲清楚“原数组相对顺序”这六个字就是加分项。3. 46.全排列与47.全排列II排列问题的去重艺术3.1 全排列和组合的本质差异全排列的思路和之前做过的组合问题有明显区别组合里选了元素2之后for循环从3开始因为组合不关心顺序[2,3]和[3,2]算同一种排列里选了元素2之后下一个位置仍然可以选元素1、3因为排列关心顺序。反映到代码上全排列的for循环不再使用startIndex而是固定从0开始遍历整个数组同时用used数组标记当前路径上哪些元素已经被使用过class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, vectorbool used) { if (path.size() nums.size()) { result.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] false; } } public: vectorvectorint permute(vectorint nums) { result.clear(); path.clear(); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };这里used数组负责的就是典型的“树枝去重”同一个排列中一个元素不能出现两次。递归到叶子时path的长度等于nums的长度说明所有元素都用了一遍收集结果。3.2 全排列II排序后如何做树层去重加入重复元素后全排列会生成大量重复结果。以[1,1,2]为例两个1可以互换位置产生两组完全相同的排列实际只需要保留其中一组。标准解法是先对数组排序让相同值相邻然后在for循环里加一条剪枝class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, vectorbool used) { if (path.size() nums.size()) { result.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] used[i - 1] false) continue; used[i] true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] false; } } public: vectorvectorint permuteUnique(vectorint nums) { result.clear(); path.clear(); sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };核心是这行if (i 0 nums[i] nums[i - 1] used[i - 1] false) continue;它剪掉的是“同一树层上的重复分支”。想象一下第一个1被选择后进入递归回溯回来时used[0]恢复为false此时for循环继续走到i1发现nums[1]等于nums[0]且used[0]false说明前一个相同值已经“功成身退”了当前这个分支和刚才那个分支本质相同直接剪掉。3.3 used[i-1]条件为什么不能写反很多同学问过这里到底用used[i-1] false还是used[i-1] true这是个极其经典的坑。如果用used[i-1] true含义变成“如果前一个相同元素当前正在路径上就跳过”。看起来像是防止两个1同时出现但实际上会导致一种情况永远被跳过吗并不会它只是把去重策略换成了另一种形态最终结果里仍可能混入重复排列。因为当路径顺序是“第二个1先被使用第一个1后使用”时两个1在排列里的值相同结果却重复了这个判断拦不住。所以标准写法一定是used[i-1] false它剪的是树层重复used[i-1] true保留的是树枝使用在排列去重场景下无法完整去重。想不通的时候拿[1,1,2]手动模拟一遍结论就清楚了。写47题时还有一个常见遗漏忘记在最开始调用sort。排序是相邻比较去重的前提条件不排序nums[i] nums[i-1]根本判断不到重复值整个hash去重的效果会失效。4. 51.N皇后二维回溯的解题范式4.1 棋盘建模与递归设计N皇后是回溯里“空间建模”最经典的一道题。题目要求n个皇后放在n×n棋盘上彼此不能在同一行、同一列、同一对角线上。暴力枚举所有摆法显然不可行回溯可以把无效分支提前剪掉。关键建模思路是每一行有且只能放一个皇后所以“行”天然可以作为递归的层数。递归函数传入当前处理的行号row在每一层的for循环里尝试0到n-1列。这样二维问题被拆成了一个合理的递归顺序第一行放哪里、第二行放哪里……逐行往下推进。class Solution { private: vectorvectorstring result; void backtracking(int n, int row, vectorstring chessboard) { if (row n) { result.push_back(chessboard); return; } for (int col 0; col n; col) { if (isValid(row, col, chessboard, n)) { chessboard[row][col] Q; backtracking(n, row 1, chessboard); chessboard[row][col] .; } } } bool isValid(int row, int col, vectorstring chessboard, int n) { for (int i 0; i row; i) { if (chessboard[i][col] Q) return false; } for (int i row - 1, j col - 1; i 0 j 0; i--, j--) { if (chessboard[i][j] Q) return false; } for (int i row - 1, j col 1; i 0 j n; i--, j) { if (chessboard[i][j] Q) return false; } return true; } public: vectorvectorstring solveNQueens(int n) { result.clear(); vectorstring chessboard(n, string(n, .)); backtracking(n, 0, chessboard); return result; } };注意这里的棋盘用了一个vector 每个元素是n个字符组成的字符串.表示空位Q表示皇后。初始化时给n行、每行n个点非常直观。4.2 isValid校验函数只查三个方向有人会问“N皇后不是要检查行、列、两条对角线吗为什么isValid里没有检查同一行”因为递归设计是逐行放皇后每一行在进入下一层递归之前只会尝试放一个皇后。你放这行皇后的时候本行之前的位置都是.之后的位置还没轮到所以同行检查天然不需要。真正需要检查的是同一列往上遍历所有已经放过的行看有没有同列皇后。左上到右下对角线从当前位置往左上方向检查。右上到左下对角线从当前位置往右上方向检查。三个for循环都只往“已经放过皇后的上方区域”检查因为下方的行还没放东西检查了也没有意义。代码里另一个值得注意的点是chessboard是引用传参每次递归后必须把chessboard[row][col]恢复成.。忘了回溯棋盘状态就会串后续分支的判断全是错的。4.3 时间复杂度与常用优化N皇后最朴素回溯的时间复杂度可以粗略估算为O(n!)。第一行有n个列可选放完第一行后第二行最多n-1个位置可选通常还会被剪枝剪掉一部分逐层递减。空间复杂度主要来自棋盘和递归栈是O(n^2)或O(n)级别。如果觉得isValid的每次O(n)检查拖慢速度可以用三个布尔数组做O(1)合法性判断colUsed[j]第j列是否被占用diag1[i - j n - 1]行减列对应的对角线是否被占用diag2[i j]行加列对应的对角线是否被占用这种优化思路适合在面试时作为加分项提出来但刷题阶段建议先把最基础的写法吃透不要一上来就叠状态数组容易把自己绕晕。5. 实战延伸最长递增子序列怎么跑进了前端框架5.1 从491题到Vue3 diff的联想看到热搜词里“vue3 diff 相对 vue2 的优化点静态提升、patchFlag、最长递增子序列”你可能觉得奇怪今天刷的是回朔算法跟前端框架有什么关系关系在于“最长递增子序列”LIS这个概念。491题研究的是“找出所有递增子序列”Vue3的diff算法里为了优化DOM节点的移动顺序需要求“旧子节点在新列表中的最长递增子序列”。一个是收集所有可能一个是求最长的那一条本质上都在研究子序列的相对顺序问题。LIS本身是LeetCode 300题标准解法是动态规划O(n²)或贪心二分O(nlogn)并不用回溯。但491题让你理解了“子序列”在算法中的形态再去看Vue3的diff优化就不会一头雾水。5.2 Vue3的静态提升与patchFlagVue2的diff是全量比较整棵虚拟DOM树即使某些节点完全静态、永远不变每次更新时也会被重新遍历一遍。数据量小还好组件复杂起来性能损耗就很明显。Vue3在编译阶段做了两项重要优化静态提升编译器识别出渲染函数里那些不依赖响应式数据的静态虚拟节点把它们提升到渲染函数外部初始化。这样每次重新渲染时静态节点直接复用同一个vnode对象不再重复创建。patchFlag动态节点会被打上标记比如动态文本、动态class、动态props等等。更新时diff只会针对带标记的节点做精确更新。框架不用再逐层猜测“这个节点到底哪里变了”而是直接按flag去patch。简单理解Vue2是“把整栋楼都重新检查一遍水电”Vue3是“只检查贴了标签的房间”。性能差距自然就拉开了。5.3 最长递增子序列如何减少DOM移动diff的核心场景之一新旧子节点列表的顺序不一致如何用最少的DOM移动次数把旧列表变成新列表Vue3的做法是先遍历新列表记录每个旧节点在新列表中的位置索引得到一个序列。然后求这个序列的LIS。LIS中的节点相对顺序已经正确可以保持原地不动其他节点围绕它们插入或移动就能把DOM操作次数压缩到最小。举个具体例子。旧顺序是[A, B, C, D, E]新顺序是[C, B, A, D, E]。把新顺序换算成旧索引A的位置是2B是1C是0D是3E是4得到序列[2, 1, 0, 3, 4]。这个序列的LIS是[0, 3, 4]对应A、D、E三个节点。这三个节点在新旧顺序里的相对关系一致不需要动只需要把B和C插到正确的位置上整个列表就转换完成。Vue3源码里实现LIS的getSequence方法用的是贪心二分的思路用一个数组记录当前找到的最长递增子序列的索引再用前驱数组回溯出真正的序列。核心逻辑和LeetCode 300题的优化解法同源。写到这里你会发现今天上午还在纠结491题的去重下午一转头同样的“递增子序列”思想已经出现在前沿前端框架的核心diff逻辑里。算法的价值很多时候就是这样——你学的时候不知道它会在哪里发光但学扎实了机会来临时你接得住。6. 常见错误与排查技巧实录6.1 四道题最容易踩的坑题目典型错误正确姿势491先排序再做子序列用每层局部set去重保持原数组顺序491set定义在函数外没eraseset放在递归函数内新建不需要回溯擦除46错误使用startIndex排列每层从0开始用used控制占用47忘记先排序递归前必须sort才能相邻比较去重47used[i-1]条件写反树层去重必须用 !used[i-1]51isValid检查同行每行只放一个皇后同行无需检查51递归后忘了撤销棋盘递归返回后把chessboard[row][col]恢复.如果发现自己提交报错先对照这张表排查大概率能解决一半以上的问题。6.2 调试递归的三个实用技巧递归最大的坑是“看不到过程”。我刷回溯题时一直用三个方法排查打印现场在每一层递归入口打印startIndex或row、当前选择的值、进入之前和回溯之后的path状态。肉眼看到状态“进入时加上退出时减去”基本就能定位逻辑错误。画树形图拿一个很小的测试样例手动画递归树。比如491用[4,6,7,7]47用[1,1,2]51用n4。对照代码逐层模拟比盯着代码空想快得多。只加不删的调试法在path.push_back()和path.pop_back()前后各打印一次path如果回溯后path没有恢复原样说明“撤销处理”这一步丢了。我一直觉得回溯题的调试重点不是“代码能不能跑”而是“状态有没有被正确复原”。只要进入递归前和回溯后状态一致剩下的就是搜索空间定义的问题。写在最后今天我刷完这四道题最大的感受是回溯模板只是一个空壳真正拉开差距的是对“搜索空间”的理解。491逼你放下排序去重的惯性改用每层局部set47逼你把树层去重和树枝去重拆开来看46让你重新认识“排列和组合到底哪里不同”51则考验你把现实棋盘抽象成递归层级的建模能力。如果你也在跟代码随想录算法训练营建议今天这四道题不要满足于AC一遍就划走。多问自己几个为什么为什么491不能排序为什么47的used条件要这样写为什么N皇后不需要检查同行这些问题想明白了以后再遇到什么新的回溯题都能往同一套框架里套。最后分享一个实用小技巧今天的四道题代码总量不大很适合在本地编辑器里全部手敲一遍然后故意改错一个条件观察输出如何变化。亲手制造一次bug比看十遍别人的题解都记得牢。