文章目录在试错的迷宫中寻找最优解一、 前言从理论走向实战二、 找出所有子集的异或总和再求和位运算子集2.1 题目描述2.2 超详细深度剖析1. 状态维护的奥秘2. ASCII 状态树图解2.3 C 代码实战三、 全排列 II带重复元素的排列与剪枝3.1 题目描述3.2 超详细深度剖析回溯必考难点1. 排序将重复扼杀在摇篮里2. 树层去重剪枝魔法3. ASCII 状态树图解剪枝过程3.3 C 代码实战四、 电话号码的字母组合独立空间的组合4.1 题目描述4.2 超详细深度剖析1. 与全排列的区别独立的备选库2. 哈希映射技巧4.3 C 代码实战五、 括号生成带动态规则的排列5.1 题目描述5.2 超详细深度剖析1. 什么是有效的括号2. 状态变量的设计5.3 C 代码实战六、 组合顺序无关的子集问题6.1 题目描述6.2 超详细深度剖析1. 组合与排列的核心差异2. 极致的数学剪枝6.3 C 代码实战七、 总结回溯进阶第一阶段在试错的迷宫中寻找最优解一、 前言从理论走向实战开篇在上一篇中我们学习了回溯算法的基石全排列与子集。它们构成了两棵最标准的状态树。核心进阶然而在实际的面试和开发中题目绝不会这么赤裸裸。它们会在标准模型上增加各种限制条件。这就是回溯算法最核心的考点——剪枝Pruning与状态维护。系列规划接下来的 15 道综合练习题是回溯算法的精华。为了保证讲解的绝对深度和细节这 15 道题我将分为上、中、下三篇为大家彻底剖析。点赞、收藏与分享本篇为上篇我们将重点攻克位运算状态、去重剪枝逻辑、独立空间组合以及规则约束。准备好发车了吗二、 找出所有子集的异或总和再求和位运算子集2.1 题目描述题目链接1863. 找出所有子集的异或总和再求和描述求数组nums中每个子集的异或总和计算并返回这些值相加之和。异或总和数组中所有元素按位 XOR 的结果空集为 0。示例输入nums [1,3]输出6解释空集(0) (1) (3) (1^32) 6。2.2 超详细深度剖析1. 状态维护的奥秘这道题的骨架就是求子集。但区别在于普通求子集是把整个数组存下来而这里我们只需要子集的异或和。异或的自反性A ^ B ^ B A。这是一个极其完美的特性意味着我们可以用一个整数变量path代替数组来记录当前状态。做选择path ^ nums[i]加入子集。恢复现场path ^ nums[i]再次异或同一个数完美抵消退出子集。2. ASCII 状态树图解以nums [5, 1, 6]为例(根节点空集path0)------------------sum0/|\选5选1选6path5path1path6sum5sum1sum6/\|选1选6选6path4path3path7sum4sum3sum7|选6path2sum2注意状态树上的每一个节点包含根节点和中间节点都是一个合法的子集。所以我们刚进入递归函数时就要把当前的path累加到全局的sum中。2.3 C 代码实战classSolution{private:intpath0;// 记录当前子集的异或和intsum0;// 记录所有子集异或和的总和public:intsubsetXORSum(vectorintnums){dfs(nums,0);returnsum;}// pos 表示当前从哪个下标开始挑选元素voiddfs(vectorintnums,intpos){// 1. 记录当前状态因为每个节点都是合法子集一进来就累加sumpath;// 2. 遍历选项为了防止选了前面的又选后面的造成重复组合必须从 pos 开始for(intipos;inums.size();i){// 3. 做出选择把当前数字异或进 pathpath^nums[i];// 4. 递归进入下一层注意下一层的起点是 i 1绝不走回头路dfs(nums,i1);// 5. 恢复现场由于 A ^ B ^ B A再次异或 nums[i] 即可撤销选择path^nums[i];}}};三、 全排列 II带重复元素的排列与剪枝3.1 题目描述题目链接47. 全排列 II描述给定一个可包含重复数字的序列nums按任意顺序返回所有不重复的全排列。示例输入nums [1,1,2]输出[[1,1,2], [1,2,1], [2,1,1]]3.2 超详细深度剖析回溯必考难点如果数组里有两个1我们标记为1 A 1_A1A和1 B 1_B1B普通的排列算法会把[ 1 A , 1 B , 2 ] [1_A, 1_B, 2][1A,1B,2]和[ 1 B , 1 A , 2 ] [1_B, 1_A, 2][1B,1A,2]算作两种不同的排列这就导致了重复。1. 排序将重复扼杀在摇篮里要发现重复必须先把相同的元素凑到一起。第一步绝对是排序sort(nums.begin(), nums.end())。2. 树层去重剪枝魔法我们定下一个强硬的规矩相同的元素必须严格按照它们在原数组中的物理顺序来使用。也就是说只有在1 A 1_A1A被用掉之后我才允许你用1 B 1_B1B。如果不按这个顺序直接跳过剪枝。剪枝逻辑判断if (i 0 nums[i] nums[i - 1] check[i - 1] false)nums[i] nums[i-1]当前元素和上一个元素一模一样。check[i-1] false上一个兄弟元素在当前这一条树枝上根本还没被用过说明你现在是在尝试把它当作这一层的新分支开头这必然会产生一模一样的重复树枝。直接 continue3. ASCII 状态树图解剪枝过程数组[1A, 1B,2][]/|\[1A][1B](剪掉!)[2]/\^ /\[..,1B][..,2]1A没用过![2,1A][2,1B](剪)|||^[1A,1B,2][1A,2,1B][2,1A,1B]1A没用过!3.3 C 代码实战classSolution{private:vectorintpath;vectorvectorintret;boolcheck[9]{false};// 题目规定长度 8public:vectorvectorintpermuteUnique(vectorintnums){// 核心第一步必须要排序让相同元素相邻sort(nums.begin(),nums.end());dfs(nums,0);returnret;}// pos 表示当前正在填排列的第几个空位voiddfs(vectorintnums,intpos){// 1. 递归出口填满了if(posnums.size()){ret.push_back(path);return;}// 2. 遍历所有可选项for(inti0;inums.size();i){// 如果已经被当前路径用过了跳过if(check[i])continue;// 【核心剪枝逻辑树层去重】// 如果和前一个元素相同并且前一个元素没有被使用// 说明此时如果用它是在开拓一条和前一个元素完全平行的重复分支必须剪掉if(i0nums[i]nums[i-1]check[i-1]false){continue;}// 3. 做出选择path.push_back(nums[i]);check[i]true;// 4. 递归下一层dfs(nums,pos1);// 5. 撤销选择恢复现场path.pop_back();check[i]false;}}};四、 电话号码的字母组合独立空间的组合4.1 题目描述题目链接17. 电话号码的字母组合描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。给出数字到字母的映射如下与电话按键相同。示例输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]4.2 超详细深度剖析1. 与全排列的区别独立的备选库在全排列中我们是从一个公共的nums数组里挑数字为了防止重复挑我们必须引入check数组。但这道题不同如果digits是23第一个坑位备选库是2对应的[a, b, c]。第二个坑位备选库是3对应的[d, e, f]。每一个坑位去哪里挑字母是完全独立且互不干扰的。所以这道题不需要check数组2. 哈希映射技巧我们需要一个全局的string hash[10]数组把hash[2]存为abc这样在递归到第pos个数字时可以直接hash[digits[pos] - 0]拿到备选字母表。4.3 C 代码实战classSolution{private:// 映射表下标对应数字内容对应按键字母string hash[10]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};string path;vectorstringret;public:vectorstringletterCombinations(string digits){// 特判空字符串直接返回空数组if(digits.size()0)returnret;dfs(digits,0);returnret;}// pos 表示当前正在处理 digits 字符串的第 pos 个字符voiddfs(stringdigits,intpos){// 1. 递归出口所有的数字都处理完了if(posdigits.size()){ret.push_back(path);return;}// 2. 拿到当前数字对应的“备选字母库”string lettershash[digits[pos]-0];// 3. 在备选库中遍历尝试每一种可能for(charch:letters){// 做选择path.push_back(ch);// 递归进入下一层处理下一个数字 (pos 1)dfs(digits,pos1);// 撤销选择恢复现场path.pop_back();}}};五、 括号生成带动态规则的排列5.1 题目描述题目链接22. 括号生成描述数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例输入n 3输出[((())),(()()),(())(),()(()),()()()]5.2 超详细深度剖析1. 什么是有效的括号我们在填坑位时每一位只有两个选择(或者)。如果是漫无目的地填肯定会生成))((这种废品。怎样通过剪枝把废品砍掉记住合法括号字符串的两个铁律从左往右看左括号的数量不能超过n。右括号的数量不能超过当前已放置的左括号数量。一旦右比左多必定闭合失败直接淘汰。2. 状态变量的设计我们需要引入两个变量left记录已使用的左括号数right记录已使用的右括号数。加左括号的条件left n。加右括号的条件right left。5.3 C 代码实战classSolution{private:intn;intleft0;// 已使用的左括号个数intright0;// 已使用的右括号个数string path;// 当前拼接的字符串vectorstringret;// 结果集public:vectorstringgenerateParenthesis(int_n){n_n;dfs();returnret;}voiddfs(){// 1. 递归出口当右括号也用完 n 个时意味着左右都用完了且合法if(rightn){ret.push_back(path);return;}// 2. 尝试添加左括号分支// 剪枝条件左括号不能超过 nif(leftn){path.push_back(();left;// 维护全局状态dfs();path.pop_back();// 恢复现场left--;}// 3. 尝试添加右括号分支// 剪枝条件右括号数量必须严格小于当前左括号的数量if(rightleft){path.push_back());right;// 维护全局状态dfs();path.pop_back();// 恢复现场right--;}}};六、 组合顺序无关的子集问题6.1 题目描述题目链接77. 组合描述给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。示例输入n 4, k 2输出[[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]6.2 超详细深度剖析1. 组合与排列的核心差异排列[1, 2]和[2, 1]是两种不同的排列。所以每一层循环都要从头0开始找配合check数组去重。组合[1, 2]和[2, 1]视为同一种组合。为了避免产生[2, 1]这种倒退的情况我们引入一个绝不回头策略。实现方法给递归函数加一个参数start规定这一层循环只能从start开始往后挑。当你挑了2传给下一层的start就是3它永远不可能再回去挑1了。这样天然就去重了。2. 极致的数学剪枝如果n 4k 4。当你第一层挑了2你还需要挑 3 个数但是后面只剩下3和4两个数了。这注定是一条死路。剪枝推导我们还需要挑的个数是k - path.size()。从i开始到n剩下的可用数字个数是n - i 1。如果要凑够必须满足n - i 1 k - path.size()。解不等式得i n - (k - path.size()) 1。把这个条件写进for循环里可以让程序快得飞起6.3 C 代码实战classSolution{private:vectorintpath;vectorvectorintret;intn,k;public:vectorvectorintcombine(int_n,int_k){n_n;k_k;dfs(1);// 从数字 1 开始挑选returnret;}// start 表示这一层必须从 start 及其后面的数字里挑voiddfs(intstart){// 1. 递归出口组合的长度达到要求 kif(path.size()k){ret.push_back(path);return;}// 2. 遍历选择// 【极致剪枝】如果剩下的数字不够填满 path 了直接终止循环// 例如n4, k3, 目前 path 空(需3个)。如果从 3 开始挑(剩3,4两个数)3 4 - 3 1 (即 3 2) 不成立直接不进循环for(intistart;in-(k-path.size())1;i){// 做出选择path.push_back(i);// 递归下一层关键传给下一层的起点是 i 1绝不回头dfs(i1);// 恢复现场path.pop_back();}}};七、 总结回溯进阶第一阶段复盘总结通过这 5 道题我们给回溯的“裸模板”穿上了几件强大的神装。位运算记录状态1863题当只需记录异或和时变量的异或和再异或就是天然的恢复现场。树层去重法47题针对含有重复元素的排列问题“排序 !check[i-1]”是降维打击的王牌。独立解空间17题如果每一层的选择库是独立的直接映射即可不需要全局check。动态合法性剪枝22题根据业务逻辑括号匹配原理动态决定分叉是否可行。顺序去重法77题针对组合问题引入start变量绝不回头配合长度剪枝是组合问题的不二法门。掌握了这些你已经能在面试中见招拆招了。在下一篇回溯大练兵中里我们将挑战更复杂的组合总和系列以及在规则怪异的数组中探索优美排列。别走开精彩继续