【递归、搜索与回溯】专题(四)：回溯算法综合大练兵（上）—— 子集、排列与组合的进阶
文章目录
在试错的迷宫中寻找最优解
一、 前言：从理论走向实战
💬 开篇：在上一篇中，我们学习了回溯算法的基石：全排列与子集。它们构成了两棵最标准的状态树。
🚀 核心进阶：然而，在实际的面试和开发中，题目绝不会这么赤裸裸。它们会在标准模型上增加各种限制条件。这就是回溯算法最核心的考点——剪枝（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 选 6
path=5 path=1 path=6
sum += 5 sum += 1 sum += 6
/ \ |
选 1 选 6 选 6
path=4 path=3 path=7
sum+=4 sum+=3 sum+=7
|
选 6
path=2
sum+=2
注意：状态树上的每一个节点（包含根节点和中间节点）都是一个合法的子集。所以，我们刚进入递归函数时，就要把当前的 path 累加到全局的 sum 中。
2.3 C++ 代码实战
class Solution {
private:
int path = 0; // 记录当前子集的异或和
int sum = 0; // 记录所有子集异或和的总和
public:
int subsetXORSum(vector<int>& nums) {
dfs(nums, 0);
return sum;
}
// pos 表示当前从哪个下标开始挑选元素
void dfs(vector<int>& nums, int pos) {
// 1. 记录当前状态：因为每个节点都是合法子集，一进来就累加
sum += path;
// 2. 遍历选项：为了防止选了前面的又选后面的造成重复组合，必须从 pos 开始
for (int i = pos; i < nums.size(); i++) {
// 3. 做出选择：把当前数字异或进 path
path ^= 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.2 超详细深度剖析（回溯必考难点）
如果数组里有两个 1（我们标记为
1
A
1_A
1A 和
1
B
1_B
1B），普通的排列算法会把
[
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_A
1A 被用掉之后，我才允许你用
1
B
1_B
1B。如果不按这个顺序，直接跳过（剪枝）。
剪枝逻辑判断：
if (i > 0 && nums[i] == nums[i - 1] && check[i - 1] == false)
nums[i] == nums[i-1]：当前元素和上一个元素一模一样。check[i-1] == false：上一个兄弟元素在当前这一条树枝上根本还没被用过！说明你现在是在尝试把它当作这一层的新分支开头，这必然会产生一模一样的重复树枝。直接 continue！
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++ 代码实战
class Solution {
private:
vector<int> path;
vector<vector<int>> ret;
bool check[9] = {false}; // 题目规定长度 <= 8
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
// 核心第一步：必须要排序！让相同元素相邻
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ret;
}
// pos 表示当前正在填排列的第几个空位
void dfs(vector<int>& nums, int pos) {
// 1. 递归出口：填满了
if (pos == nums.size()) {
ret.push_back(path);
return;
}
// 2. 遍历所有可选项
for (int i = 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++ 代码实战
class Solution {
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) return ret;
dfs(digits, 0);
return ret;
}
// pos 表示当前正在处理 digits 字符串的第 pos 个字符
void dfs(string& digits, int pos) {
// 1. 递归出口：所有的数字都处理完了
if (pos == digits.size()) {
ret.push_back(path);
return;
}
// 2. 拿到当前数字对应的“备选字母库”
string letters = hash[digits[pos] - '0'];
// 3. 在备选库中遍历，尝试每一种可能
for (char ch : 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++ 代码实战
class Solution {
private:
int n;
int left = 0; // 已使用的左括号个数
int right = 0; // 已使用的右括号个数
string path; // 当前拼接的字符串
vector<string> ret; // 结果集
public:
vector<string> generateParenthesis(int _n) {
n = _n;
dfs();
return ret;
}
void dfs() {
// 1. 递归出口：当右括号也用完 n 个时，意味着左右都用完了，且合法
if (right == n) {
ret.push_back(path);
return;
}
// 2. 尝试添加左括号分支
// 剪枝条件：左括号不能超过 n
if (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++ 代码实战
class Solution {
private:
vector<int> path;
vector<vector<int>> ret;
int n, k;
public:
vector<vector<int>> combine(int _n, int _k) {
n = _n;
k = _k;
dfs(1); // 从数字 1 开始挑选
return ret;
}
// start 表示这一层必须从 start 及其后面的数字里挑
void dfs(int start) {
// 1. 递归出口：组合的长度达到要求 k
if (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 (int i = start; i <= n - (k - path.size()) + 1; i++) {
// 做出选择
path.push_back(i);
// 递归下一层，关键：传给下一层的起点是 i + 1，绝不回头！
dfs(i + 1);
// 恢复现场
path.pop_back();
}
}
};
七、 总结：回溯进阶第一阶段
💬 复盘总结：通过这 5 道题，我们给回溯的“裸模板”穿上了几件强大的神装。
- 位运算记录状态（1863题）：当只需记录异或和时，变量的异或和再异或就是天然的恢复现场。
- 树层去重法（47题）：针对含有重复元素的排列问题，“排序 +
!check[i-1]” 是降维打击的王牌。 - 独立解空间（17题）：如果每一层的选择库是独立的，直接映射即可，不需要全局
check。 - 动态合法性剪枝（22题）：根据业务逻辑（括号匹配原理）动态决定分叉是否可行。
- 顺序去重法（77题）：针对组合问题，引入
start变量，绝不回头，配合长度剪枝，是组合问题的不二法门。
掌握了这些，你已经能在面试中见招拆招了。
在下一篇 回溯大练兵（中） 里，我们将挑战更复杂的组合总和系列，以及在规则怪异的数组中探索优美排列。别走开，精彩继续！ 🚀
更多推荐
7
0- 0
已为社区贡献3条内容
所有评论(0)