深度优先搜索（DFS）与回溯法：从全排列到子集问题的决策树与剪枝优化

🕗 发布于 2024-12-13 07:23 深度优先决策树剪枝 c++ 算法

在这里插入图片描述

文章目录

前言
结语

前言

深度优先搜索（DFS）和回溯法是解决复杂问题中不可或缺的算法工具，尤其在组合问题（如全排列、子集等）中，发挥着至关重要的作用。通过递归的方式，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;
            }
        }
    }
};

✨时间和空间复杂度

🎁1. 时间复杂度

每个排列需要遍历 nums 的所有元素，同时需要递归构造排列。
全排列的总数为 $n!$ ，其中 n 为 nums 的长度。
每次构造排列需要 $O (n)$ 的时间复杂度，因此总时间复杂度为： $O (n \cdot n!)$

🎁2. 空间复杂度

递归深度为 $O (n)$ ，对应递归栈的最大深度。
存储结果的 ret 大小为 $O (n \cdot n!)$ （每个排列长度为 n，共有 n! 个排列）。
额外空间为 path 和 check，均为 $O(n) $。
总空间复杂度为： $O (n \cdot n!)$

🎄二、子集

题目链接：https://leetcode.cn/problems/subsets/description/

✨解法一：逐位置决策法

核心思想：对于每个位置，都需要明确“选”或者“不选”两种可能，然后继续对后续位置进行递归。

🎁步骤分析

输入数组：nums = [1, 2, 3]。
决策树构造：
- 对于每个元素，存在两个分支：选它和不选它。
- 递归过程中，我们先“选”再“回溯”，然后“跳过当前元素”。
递归终止条件：
- 当递归位置 pos 达到数组末尾（pos == nums.size()）时，将当前路径 path 加入结果集 ret。

🎁运行示例

初始调用：dfs(nums, 0)
- 选1：path = [1]，递归进入 dfs(nums, 1)
  - 选2：path = [1, 2]，递归进入 dfs(nums, 2)
    - 选3：path = [1, 2, 3]，递归终止，保存结果 [[1, 2, 3]]
    - 回溯到选2状态：path = [1, 2]
    - 不选3：path = [1, 2]，递归终止，保存结果 [[1, 2, 3], [1, 2]]
  - 回溯到选1状态：path = [1]
  - 不选2：path = [1]，递归进入 dfs(nums, 2)
    - 选3：path = [1, 3]，递归终止，保存结果 [[1, 2, 3], [1, 2], [1, 3]]
    - 不选3：path = [1]，递归终止，保存结果 [[1, 2, 3], [1, 2], [1, 3], [1]]
- 回溯到初始状态：path = []
- 不选1：path = []，递归进入 dfs(nums, 1)
  - 选2：path = [2]，递归类似上面。
  - 不选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 开始，依次向后选择元素，尝试递归。

🎁运行示例

初始调用：dfs(nums, 0)
- 当前路径为空，加入结果集：ret = [[]]
- 从 pos = 0 开始：
  - 选1：path = [1]，加入结果集：ret = [[], [1]]，递归进入 dfs(nums, 1)
    - 选2：path = [1, 2]，加入结果集：ret = [[], [1], [1, 2]]，递归进入 dfs(nums, 2)
      - 选3：path = [1, 2, 3]，加入结果集：ret = [[], [1], [1, 2], [1, 2, 3]]
      - 回溯到选2状态：path = [1, 2]
    - 回溯到选1状态：path = [1]
  - 回溯到初始状态：path = []
  - 选2：递归同上。
  - 选3：递归继续。

如图分析：

在这里插入图片描述

🎁代码

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();
        }
    }
};

✨时间复杂度分析

🎁解法一

决策树分析：
- 每个元素有两种选择（选或不选），对于长度为 n 的数组，共有 2^n 种子集。
- 递归的每一步都对应一个子集的生成，因此遍历整个决策树需要 O(2^n) 的时间。
额外操作：
- 每次递归终止时，将当前路径 path 加入结果，需要 O(n) 的时间（复制 path 的内容）。

总时间复杂度：
$O(2^n⋅n)$

🎁解法二

决策树分析：
- 每个元素被递归遍历一次，所有可能的子集共 2^n 个。
- 递归过程中，每次递归都会将当前路径 path 加入结果集 ret。
额外操作：
- 每次将路径加入结果集也需要 O(n) 的时间（复制 path）。

总时间复杂度：
O(2n⋅n)

✨空间复杂度分析

🎁解法一

递归深度：
- 递归调用的最大深度为数组长度 n ，因此递归栈的空间复杂度为 $O (n)$ 。
路径存储：
- path 需要存储当前路径，大小为 $O (n)$ 。
结果集：
- 最终结果集 ret 包含 $2^n$ 个子集，每个子集的平均长度为 $O (n /2)$ ，因此结果集的存储空间为： $O (2 n \cdot n)$

总空间复杂度：
$O(2^n \cdot n)$
（递归栈和路径空间较小，可忽略不计）

🎁解法二

递归深度：
- 递归调用的最大深度为数组长度 n，因此递归栈的空间复杂度为 $O (n)$ 。
路径存储：
- path 需要存储当前路径，大小为 $O (n)$ 。
结果集：
- 同解法一，结果集需要 $O(2^n \cdot n) $的空间。

总空间复杂度：
$O(2^n \cdot n)$
（递归栈和路径空间较小，可忽略不计）

🎄三、找出所有子集的异或总和再求和

题目链接：https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/

✨解法简介

题目要求求出数组中所有子集的异或和的总和。解法采用 回溯法 (Backtracking)，枚举所有子集，同时计算每个子集的异或和，并将其累加到结果中。

✨解法步骤

🎁Step 1: 初始化变量

ret：最终结果，用于存储所有子集的异或和的累加值。
path：当前路径变量，表示当前子集的异或值。
nums：输入数组。

🎁Step 2: 回溯递归函数设计

递归函数 dfs(nums, pos)：

功能：
- 遍历以 pos 为起点的所有可能子集。
- 累加每个子集的异或值到 ret。
核心逻辑：
- 累加当前路径的异或值到 ret：每次递归进入时，将当前路径的异或值（path）加入到结果中。
- 枚举后续元素：从当前 pos 开始，逐一尝试将后续元素加入路径 path，并递归处理。
- 回溯：在递归返回后，撤销当前选择（通过异或运算恢复 path 的值）。
递归终止条件：
- 无需显式终止条件，因为递归自然会遍历所有子集，当 pos 超出数组范围时，循环自动结束。

🎁Step 3: 主函数调用

在主函数 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];
        }
    }
};

✨时间与空间复杂度

🎁时间复杂度

子集数量：对于数组长度为 $n$ ，共有 $2^n$ 个子集。
异或计算：每次递归执行异或操作的时间复杂度为 $O (1)$ 。
总复杂度： $O(2^n)$

🎁空间复杂度

递归深度：递归调用栈的最大深度为 $n$ 。
路径变量：path 是一个整数，占用 $O (1)$ 的空间。
总复杂度： $O (n)$

🎄四、全排列II

题目链接：https://leetcode.cn/problems/permutations-ii/description/

✨解法简介

利用 回溯法 (Backtracking) 生成所有排列，通过排序和剪枝（跳过重复元素）来避免生成重复排列。

✨步骤详解

🎁Step 1: 初始化

变量说明：
- ret：存储所有结果的二维数组。
- path：当前路径，用于构造一个排列。
- check：布尔数组，记录每个元素是否已经被使用过。
预处理：
- 对输入数组 nums 进行排序：sort(nums.begin(), nums.end())。
  - 排序的目的是将相同的元素放在一起，方便后续剪枝操作。

🎁Step 2: 回溯递归函数设计

递归函数 dfs(nums, pos)：

递归终止条件：
- 如果当前路径 path 的大小等于数组 nums 的长度，说明构造了一组完整排列，将其加入结果集 ret。
循环遍历每个元素：
- 遍历 nums 中的每个元素，尝试将未被使用的元素加入当前路径。
剪枝条件：
- 元素未被使用：通过 check[i] == false 判断当前元素是否可用。
- 跳过重复元素：
  - nums[i] == nums[i - 1]：当前元素与前一个元素相同。
  - check[i - 1] == false：前一个相同的元素尚未被使用，说明该排列已经处理过，直接跳过当前分支。
递归和回溯：
- 递归调用：
  - 将当前元素加入路径，标记为已使用。
  - 递归处理下一个位置。
- 回溯操作：
  - 递归返回后，将当前元素移出路径，标记为未使用，恢复状态。

🎁Step 3: 主函数调用

在主函数 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;
            }
        }
    }

✨时间与空间复杂度

🎁时间复杂度

全排列生成：
- 数组长度为 $n$ ，排列数量为 $n!$ 。
剪枝优化：
- 剪枝减少重复分支，但在最坏情况下仍需要生成 $n!$ 个排列。

总时间复杂度： $\cdot n!)$

🎁空间复杂度

递归深度：
- 递归调用栈的深度为 $O (n)$ 。
路径和标记数组：
- 路径数组 path 和布尔数组 check 的大小为 $O (n)$ 。

总空间复杂度： $O (n)$

结语

回溯法与深度优先搜索（DFS）结合，能有效地解决多种组合问题。通过决策树的结构，回溯法逐步探索解空间，而剪枝则通过减少不必要的计算，显著提高算法的效率。针对特定问题的剪枝优化，可以进一步提升回溯法的性能。

希望通过本文的讲解，您能深入理解回溯法与DFS在解决组合问题中的应用，并通过剪枝技术优化算法效率。如果您对回溯算法或其他算法问题有任何疑问，欢迎交流与讨论！

在这里插入图片描述

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！

在这里插入图片描述

原文地址：https://blog.csdn.net/suye050331/article/details/144438385

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

深度优先搜索（DFS）与回溯法：从全排列到子集问题的决策树与剪枝优化

文章目录

前言

🎄一、全排列

✨核心思路

✨实现步骤

✨代码

✨时间和空间复杂度

🎁1. 时间复杂度

🎁2. 空间复杂度

🎄二、子集

✨解法一：逐位置决策法

🎁步骤分析

🎁运行示例

🎁代码

✨解法二：逐元素扩展法

🎁步骤分析

🎁运行示例

🎁代码

✨时间复杂度分析

🎁解法一

🎁解法二

✨空间复杂度分析

🎁解法一

🎁解法二

🎄三、找出所有子集的异或总和再求和

✨解法简介

✨解法步骤

🎁Step 1: 初始化变量

🎁Step 2: 回溯递归函数设计

🎁Step 3: 主函数调用

✨代码

✨时间与空间复杂度

🎁时间复杂度

🎁空间复杂度

🎄四、全排列II

✨解法简介

✨步骤详解

🎁Step 1: 初始化

🎁Step 2: 回溯递归函数设计

🎁Step 3: 主函数调用

✨代码

✨时间与空间复杂度

🎁时间复杂度

🎁空间复杂度

结语

相关文章