当前位置：首页 > news >正文

【递归、搜索与回溯】专题(四)：回溯算法综合大练兵（上）—— 子集、排列与组合的进阶

news 2026/3/26 17:52:56

文章目录

在试错的迷宫中寻找最优解

一、前言：从理论走向实战

💬开篇：在上一篇中，我们学习了回溯算法的基石：全排列与子集。它们构成了两棵最标准的状态树。
🚀核心进阶：然而，在实际的面试和开发中，题目绝不会这么赤裸裸。它们会在标准模型上增加各种限制条件。这就是回溯算法最核心的考点——剪枝（Pruning）与状态维护。
💡系列规划：接下来的 15 道综合练习题是回溯算法的精华。为了保证讲解的绝对深度和细节，这 15 道题我将分为上、中、下三篇为大家彻底剖析。
👍点赞、收藏与分享：本篇为（上）篇，我们将重点攻克位运算状态、去重剪枝逻辑、独立空间组合以及规则约束。准备好发车了吗？

二、找出所有子集的异或总和再求和（位运算+子集）

2.1 题目描述

题目链接：1863. 找出所有子集的异或总和再求和
描述：
求数组nums中每个子集的异或总和，计算并返回这些值相加之和。
（异或总和：数组中所有元素按位 XOR 的结果；空集为 0）。
示例：
输入：nums = [1,3]
输出：6
解释：空集(0) +(1) +(3) +(1^3=2) = 6。

2.2 超详细深度剖析

1. 状态维护的奥秘

这道题的骨架就是求子集。但区别在于：普通求子集是把整个数组存下来，而这里我们只需要子集的异或和。

异或的自反性：A ^ B ^ B = A。这是一个极其完美的特性！
意味着我们可以用一个整数变量path代替数组来记录当前状态。
做选择：path ^= nums[i]（加入子集）。
恢复现场：path ^= nums[i]（再次异或同一个数，完美抵消，退出子集）。

2. ASCII 状态树图解

以nums = [5, 1, 6]为例：

(根节点，空集，path=0)------------------sum+=0/|\选5选1选6path=5path=1path=6sum+=5sum+=1sum+=6/\|选1选6选6path=4path=3path=7sum+=4sum+=3sum+=7|选6path=2sum+=2

注意：状态树上的每一个节点（包含根节点和中间节点）都是一个合法的子集。所以，我们刚进入递归函数时，就要把当前的path累加到全局的sum中。

2.3 C++ 代码实战

classSolution{private:intpath=0;// 记录当前子集的异或和intsum=0;// 记录所有子集异或和的总和public:intsubsetXORSum(vector<int>&nums){dfs(nums,0);returnsum;}// pos 表示当前从哪个下标开始挑选元素voiddfs(vector<int>&nums,intpos){// 1. 记录当前状态：因为每个节点都是合法子集，一进来就累加sum+=path;// 2. 遍历选项：为了防止选了前面的又选后面的造成重复组合，必须从 pos 开始for(inti=pos;i<nums.size();i++){// 3. 做出选择：把当前数字异或进 pathpath^=nums[i];// 4. 递归进入下一层：注意下一层的起点是 i + 1，绝不走回头路dfs(nums,i+1);// 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. 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:vector<int>path;vector<vector<int>>ret;boolcheck[9]={false};// 题目规定长度 <= 8public:vector<vector<int>>permuteUnique(vector<int>&nums){// 核心第一步：必须要排序！让相同元素相邻sort(nums.begin(),nums.end());dfs(nums,0);returnret;}// pos 表示当前正在填排列的第几个空位voiddfs(vector<int>&nums,intpos){// 1. 递归出口：填满了if(pos==nums.size()){ret.push_back(path);return;}// 2. 遍历所有可选项for(inti=0;i<nums.size();i++){// 如果已经被当前路径用过了，跳过if(check[i])continue;// 【核心剪枝逻辑：树层去重】// 如果和前一个元素相同，并且前一个元素没有被使用// 说明此时如果用它，是在开拓一条和前一个元素完全平行的重复分支，必须剪掉！if(i>0&&nums[i]==nums[i-1]&&check[i-1]==false){continue;}// 3. 做出选择path.push_back(nums[i]);check[i]=true;// 4. 递归下一层dfs(nums,pos+1);// 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;vector<string>ret;public:vector<string>letterCombinations(string digits){// 特判：空字符串直接返回空数组if(digits.size()==0)returnret;dfs(digits,0);returnret;}// pos 表示当前正在处理 digits 字符串的第 pos 个字符voiddfs(string&digits,intpos){// 1. 递归出口：所有的数字都处理完了if(pos==digits.size()){ret.push_back(path);return;}// 2. 拿到当前数字对应的“备选字母库”string letters=hash[digits[pos]-'0'];// 3. 在备选库中遍历，尝试每一种可能for(charch:letters){// 做选择path.push_back(ch);// 递归进入下一层，处理下一个数字 (pos + 1)dfs(digits,pos+1);// 撤销选择，恢复现场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;intleft=0;// 已使用的左括号个数intright=0;// 已使用的右括号个数string path;// 当前拼接的字符串vector<string>ret;// 结果集public:vector<string>generateParenthesis(int_n){n=_n;dfs();returnret;}voiddfs(){// 1. 递归出口：当右括号也用完 n 个时，意味着左右都用完了，且合法if(right==n){ret.push_back(path);return;}// 2. 尝试添加左括号分支// 剪枝条件：左括号不能超过 nif(left<n){path.push_back('(');left++;// 维护全局状态dfs();path.pop_back();// 恢复现场left--;}// 3. 尝试添加右括号分支// 剪枝条件：右括号数量必须严格小于当前左括号的数量if(right<left){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 = 4，k = 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:vector<int>path;vector<vector<int>>ret;intn,k;public:vector<vector<int>>combine(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 了，直接终止循环// 例如：n=4, k=3, 目前 path 空(需3个)。如果从 3 开始挑(剩3,4两个数)，3 <= 4 - 3 + 1 (即 3 <= 2) 不成立，直接不进循环for(inti=start;i<=n-(k-path.size())+1;i++){// 做出选择path.push_back(i);// 递归下一层，关键：传给下一层的起点是 i + 1，绝不回头！dfs(i+1);// 恢复现场path.pop_back();}}};