C++算法
深度优先搜索（DFS）与回溯法：全排列与子集问题的决策树及剪枝优化
介绍深度优先搜索（DFS）与回溯法在组合问题中的应用，涵盖全排列、子集生成、异或总和计算及去重全排列。通过决策树模型解析递归逻辑，详细讲解剪枝优化策略以降低时间复杂度。提供 C++ 代码实现及时间与空间复杂度分析，帮助理解算法核心思想与性能评估。
介绍深度优先搜索（DFS）与回溯法在组合问题中的应用，涵盖全排列、子集生成、异或总和计算及去重全排列。通过决策树模型解析递归逻辑，详细讲解剪枝优化策略以降低时间复杂度。提供 C++ 代码实现及时间与空间复杂度分析，帮助理解算法核心思想与性能评估。
深度优先搜索（DFS）和回溯法是解决复杂问题中不可或缺的算法工具，尤其在组合问题（如全排列、子集等）中，发挥着至关重要的作用。通过递归的方式，DFS 能够遍历问题的解空间，而回溯法则通过撤销不合法的选择，避免重复计算，提高效率。在解题过程中，剪枝是优化回溯法的重要手段，它通过提前排除无效路径，进一步减少了运算的复杂度。
题目链接：https://leetcode.cn/problems/permutations/description/
这段代码实现了生成一个数组的所有排列（Permutation），并返回所有可能的排列列表。采用了**深度优先搜索（DFS）**的方式，配合一个 check 数组来记录哪些元素已经使用过，从而避免重复使用。
vector<vector<int>> ret：存储最终结果，包含所有排列。vector<int> path：存储当前正在构造的排列。bool check[7]：标记数组，记录某个位置是否已经被使用，避免重复选择。默认全为 false。permute：
dfs(nums) 开始进行递归遍历，寻找所有排列。ret。dfs：
path 的长度等于 nums.size()，说明已经构造出一个完整的排列，将其加入结果集 ret。check[i] == false）。path，同时更新 check[i] = true。dfs(nums)，继续构造排列。path.pop_back()。check[i] = false，允许后续尝试其他路径。如图分析：
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[7];
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
void dfs(vector<int>& nums) {
if (path.size() == nums.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (check[i] == false) {
path.push_back(nums[i]);
check[i] = true;
dfs(nums);
path.pop_back();
check[i] = false;
}
}
}
};
nums 的所有元素，同时需要递归构造排列。nums 的长度。ret 大小为 O(n · n!)（每个排列长度为 n，共有 n! 个排列）。path 和 check，均为 O(n)。题目链接：https://leetcode.cn/problems/subsets/description/
核心思想：对于每个位置，都需要明确'选'或者'不选'两种可能，然后继续对后续位置进行递归。
nums = [1, 2, 3]。pos 达到数组末尾（pos == nums.size()）时，将当前路径 path 加入结果集 ret。dfs(nums, 0)
path = [1]，递归进入 dfs(nums, 1)
path = [1, 2]，递归进入 dfs(nums, 2)
path = [1, 2, 3]，递归终止，保存结果 [[1, 2, 3]]path = [1, 2]path = [1, 2]，递归终止，保存结果 [[1, 2, 3], [1, 2]]path = [1]path = [1]，递归进入 dfs(nums, 2)
path = [1, 3]，递归终止，保存结果 [[1, 2, 3], [1, 2], [1, 3]]path = [1]，递归终止，保存结果 [[1, 2, 3], [1, 2], [1, 3], [1]]path = []path = []，递归进入 dfs(nums, 1)
path = [2]，递归类似上面。path = []，递归继续处理后续。最终得到所有子集。
如图分析：
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos) {
if (pos == nums.size()) {
ret.push_back(path);
return;
}
// 选
path.push_back(nums[pos]);
dfs(nums, pos + 1);
// 回溯 -> 恢复现场
path.pop_back();
// 不选
dfs(nums, pos + 1);
}
};
核心思想：直接将当前路径加入结果集，然后从当前位置逐个向后选取元素递归。
nums = [1, 2, 3]。pos 开始，依次向后选择元素，尝试递归。ret = [[]]pos = 0 开始：
path = [1]，加入结果集：ret = [[], [1]]，递归进入 dfs(nums, 1)
path = [1, 2]，加入结果集：ret = [[], [1], [1, 2]]，递归进入 dfs(nums, 2)
path = [1, 2, 3]，加入结果集：ret = [[], [1], [1, 2], [1, 2, 3]]path = [1, 2]path = [1]path = []如图分析：
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos) {
ret.push_back(path);
for (int i = pos; i < nums.size(); i++) {
path.push_back(nums[i]);
dfs(nums, i + 1);
// 回溯 -> 恢复现场
path.pop_back();
}
}
};
path 加入结果，需要 O(n) 的时间（复制 path 的内容）。总时间复杂度：O(2^n · n)
path 加入结果集 ret。path）。总时间复杂度：O(2^n · n)
path 需要存储当前路径，大小为 O(n)。ret 包含 2^n 个子集，每个子集的平均长度为 O(n/2)，因此结果集的存储空间为：O(2^n · n)总空间复杂度：O(2^n · n)（递归栈和路径空间较小，可忽略不计）
path 需要存储当前路径，大小为 O(n)。总空间复杂度：O(2^n · n)（递归栈和路径空间较小，可忽略不计）
题目链接：https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/
题目要求求出数组中所有子集的异或和的总和。解法采用 回溯法 (Backtracking)，枚举所有子集，同时计算每个子集的异或和，并将其累加到结果中。
ret：最终结果，用于存储所有子集的异或和的累加值。path：当前路径变量，表示当前子集的异或值。nums：输入数组。递归函数 dfs(nums, pos)：
pos 为起点的所有可能子集。ret。ret：每次递归进入时，将当前路径的异或值（path）加入到结果中。pos 开始，逐一尝试将后续元素加入路径 path，并递归处理。path 的值）。pos 超出数组范围时，循环自动结束。在主函数 subsetXORSum 中：
ret = 0。dfs(nums, 0)，从数组的第 0 个位置开始递归。ret。如图分析：
class Solution {
public:
int ret = 0;
int path = 0;
int subsetXORSum(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos) {
ret += path;
for (int i = pos; i < nums.size(); i++) {
path ^= nums[i];
dfs(nums, i + 1);
// 回溯
path ^= nums[i];
}
}
};
path 是一个整数，占用 O(1) 的空间。题目链接：https://leetcode.cn/problems/permutations-ii/description/
利用 回溯法 (Backtracking) 生成所有排列，通过排序和剪枝（跳过重复元素）来避免生成重复排列。
ret：存储所有结果的二维数组。path：当前路径，用于构造一个排列。check：布尔数组，记录每个元素是否已经被使用过。nums 进行排序：sort(nums.begin(), nums.end())。
递归函数 dfs(nums, pos)：
path 的大小等于数组 nums 的长度，说明构造了一组完整排列，将其加入结果集 ret。nums 中的每个元素，尝试将未被使用的元素加入当前路径。check[i] == false 判断当前元素是否可用。nums[i] == nums[i - 1]：当前元素与前一个元素相同。check[i - 1] == false：前一个相同的元素尚未被使用，说明该排列已经处理过，直接跳过当前分支。在主函数 permuteUnique 中：
sort(nums.begin(), nums.end())。check 的大小为 nums.size()，初始值为 false。dfs(nums, 0)。ret。如图分析：
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[9];
vector<vector<int>> permuteUnique(vector<int>& nums) {
// 先排序
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos) {
if (path.size() == nums.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 剪枝（只关心合法分支）
if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
path.push_back(nums[i]);
check[i] = true;
dfs(nums, pos + 1);
// 回溯
path.pop_back();
check[i] = false;
}
}
}
};
总时间复杂度：O(n · n!)
path 和布尔数组 check 的大小为 O(n)。总空间复杂度：O(n)
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online