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

穷举vs暴搜vs深搜vs回溯vs剪枝（典型算法思想）—— OJ例题算法解析思路

article 2025/3/1 23:32:03

回溯算法的模版

void backtrack(vector<int>& path, vector<int>& choice, ...) 
{
    // 满⾜结束条件
    if (/* 满⾜结束条件 */) 
    {
        // 将路径添加到结果集中
        res.push_back(path);
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < choices.size(); i++) 
    {
        // 做出选择
        path.push_back(choices[i]);
        // 做出当前选择后继续搜索
        backtrack(path, choices);
        // 撤销选择
        path.pop_back();
    }
}

目录

回溯算法的模版

一、46. 全排列 - 力扣（LeetCode）

算法代码：

1. 类的成员变量

2. permute 函数

3. dfs 函数

4. 回溯的核心思想

5. 代码的优化空间

6. 代码的复杂度分析

7. 代码的改进版本

总结

二、78. 子集 - 力扣（LeetCode） 

递归流程：

解法一：算法代码（剪枝->回溯->递归出口） 

1. 类的成员变量

2. subsets 函数

3. dfs 函数

4. 回溯的核心思想

5. 代码的优化空间

6. 代码的复杂度分析

7. 代码的改进版本（避免重复子集）

改进点：

8. 总结

解法二：算法代码（回溯->剪枝->递归出口）

1. 类的成员变量

2. subsets 函数

3. dfs 函数

4. 代码的核心思想

5. 代码的优化空间

6. 代码的复杂度分析

7. 代码的改进版本（避免重复子集）

改进点：

8. 总结

一、46. 全排列 - 力扣（LeetCode）

算法代码：

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool check[7];

public:
    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]) {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回溯 -> 恢复现场
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

1. 类的成员变量

  • ret：用于存储所有可能的排列结果，类型为 vector<vector<int>>。

  • path：用于存储当前正在构建的排列，类型为 vector<int>。

  • check：用于标记某个元素是否已经被使用过，类型为 bool 数组，大小为 7（假设输入数组的长度不超过 7）。

2. permute 函数

  • 这是主函数，接收一个整数数组 nums 作为输入，并返回所有可能的排列。

  • 调用 dfs(nums) 开始深度优先搜索。

  • 最终返回 ret，即所有排列的结果。

3. dfs 函数

  • 这是递归函数，用于生成所有可能的排列。

  • 递归终止条件：如果 path 的大小等于 nums 的大小，说明当前 path 已经是一个完整的排列，将其加入到 ret 中，并返回。

  • 递归过程：

    • 遍历 nums 数组中的每一个元素。

    • 如果当前元素没有被使用过（check[i] == false），则将其加入到 path 中，并标记为已使用。

    • 递归调用 dfs，继续生成下一个位置的元素。

    • 回溯：在递归返回后，撤销当前的选择（即从 path 中移除最后一个元素，并将 check[i] 重新标记为未使用），以便尝试其他可能的排列。

4. 回溯的核心思想

  • 回溯是一种通过递归来尝试所有可能的选择，并在每一步撤销选择以回到上一步的算法。

  • 在这段代码中，回溯体现在 path.pop_back() 和 check[i] = false 这两行代码上。它们的作用是撤销当前的选择，以便尝试其他可能的排列。

5. 代码的优化空间

  • check 数组的大小是固定的 7，这意味着如果 nums 的大小超过 7，代码将无法正确处理。可以将 check 数组的大小动态设置为 nums.size()。

  • 可以使用 std::swap 来直接在原数组上进行排列，从而减少 path 和 check 的使用，进一步优化空间复杂度。

6. 代码的复杂度分析

  • 时间复杂度：O(n!)，其中 n 是 nums 的大小。因为全排列的数量是 n!。

  • 空间复杂度：O(n!)，用于存储所有排列的结果。递归栈的深度为 n，因此递归的空间复杂度为 O(n)。

7. 代码的改进版本

class Solution {
    vector<vector<int>> ret;

public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int start) {
        if (start == nums.size()) {
            ret.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            dfs(nums, start + 1);
            swap(nums[start], nums[i]); // 回溯
        }
    }
};

在这个改进版本中，我们直接在原数组上进行排列，减少了 path 和 check 的使用，从而优化了空间复杂度。

总结

这段代码通过深度优先搜索和回溯的思想，实现了全排列的生成。代码的核心在于递归和回溯的处理，通过撤销选择来尝试所有可能的排列。

二、78. 子集 - 力扣（LeetCode） 

递归流程：

解法一：算法代码（剪枝->回溯->递归出口） 

// 解法⼀：
class Solution {
    vector<vector<int>> ret;
    vector<int> path;

public:
    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);
    }
};

1. 类的成员变量

  • ret：用于存储所有子集的结果，类型为 vector<vector<int>>。

  • path：用于存储当前正在构建的子集，类型为 vector<int>。

2. subsets 函数

  • 这是主函数，接收一个整数数组 nums 作为输入，并返回所有可能的子集。

  • 调用 dfs(nums, 0) 开始深度优先搜索，0 表示从数组的第一个元素开始处理。

  • 最终返回 ret，即所有子集的结果。

3. dfs 函数

  • 这是递归函数，用于生成所有可能的子集。

  • 递归终止条件：如果 pos 等于 nums 的大小，说明已经处理完所有元素，此时 path 中存储的就是一个子集，将其加入到 ret 中，并返回。

  • 递归过程：

    1. 选择当前元素：

      • 将 nums[pos] 加入到 path 中。

      • 递归调用 dfs(nums, pos + 1)，继续处理下一个元素。

      • 在递归返回后，撤销选择（即从 path 中移除最后一个元素），以便尝试不选择当前元素的情况。

    2. 不选择当前元素：

      • 直接递归调用 dfs(nums, pos + 1)，跳过当前元素，继续处理下一个元素。

4. 回溯的核心思想

  • 回溯是一种通过递归来尝试所有可能的选择，并在每一步撤销选择以回到上一步的算法。

  • 在这段代码中，回溯体现在 path.pop_back() 这一行代码上。它的作用是撤销当前的选择，以便尝试不选择当前元素的情况。

5. 代码的优化空间

  • 如果输入数组 nums 中包含重复元素，这段代码会生成重复的子集。可以通过排序和剪枝来避免重复子集的生成。

  • 可以将 path 改为引用传递，减少拷贝的开销。

6. 代码的复杂度分析

  • 时间复杂度：O(2^n)，其中 n 是 nums 的大小。因为每个元素有两种选择（选或不选），总共有 2^n 个子集。

  • 空间复杂度：O(n)，递归栈的深度为 n。结果存储空间不计入空间复杂度。

7. 代码的改进版本（避免重复子集）

如果输入数组 nums 中包含重复元素，可以通过排序和剪枝来避免生成重复的子集。改进后的代码如下：

class Solution {
    vector<vector<int>> ret;
    vector<int> path;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序，便于剪枝
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        ret.push_back(path); // 每次递归都加入当前子集
        for (int i = pos; i < nums.size(); i++) {
            if (i > pos && nums[i] == nums[i - 1]) continue; // 剪枝，避免重复
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back(); // 回溯
        }
    }
};
改进点：

  1. 排序：先对 nums 排序，使得相同的元素相邻。

  2. 剪枝：在递归过程中，如果当前元素和前一个元素相同，并且不是第一次遇到该元素，则跳过，避免重复子集。

  3. 提前加入子集：在每次递归开始时，直接将当前 path 加入到 ret 中，这样可以避免在递归终止时才加入子集。

8. 总结

        这段代码通过深度优先搜索和回溯的思想，实现了求解数组的所有子集。代码的核心在于对每个元素的选择和不选择两种情况的分支处理，并通过回溯撤销选择以尝试其他可能性。如果输入数组包含重复元素，可以通过排序和剪枝来优化，避免生成重复子集。

解法二：算法代码（回溯->剪枝->递归出口）

// 解法⼆：
class Solution {
    vector<vector<int>> ret;
    vector<int> path;

public:
    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(); // 恢复现场
        }
    }
};

1. 类的成员变量

  • ret：用于存储所有子集的结果，类型为 vector<vector<int>>。

  • path：用于存储当前正在构建的子集，类型为 vector<int>。

2. subsets 函数

  • 这是主函数，接收一个整数数组 nums 作为输入，并返回所有可能的子集。

  • 调用 dfs(nums, 0) 开始深度优先搜索，0 表示从数组的第一个元素开始处理。

  • 最终返回 ret，即所有子集的结果。

3. dfs 函数

  • 这是递归函数，用于生成所有可能的子集。

  • 递归过程：

    1. 将当前子集加入结果：

      • 在每次递归调用开始时，直接将当前 path 加入到 ret 中。这是因为 path 在每一层递归中都表示一个有效的子集。

    2. 遍历数组元素：

      • 从当前位置 pos 开始遍历 nums 数组。

      • 将当前元素 nums[i] 加入到 path 中，表示选择该元素。

      • 递归调用 dfs(nums, i + 1)，继续处理下一个元素。

      • 在递归返回后，撤销选择（即从 path 中移除最后一个元素），以便尝试其他可能的子集。

4. 代码的核心思想

  • 子集的生成：

    • 子集的生成可以看作是对每个元素的选择或不选择。

    • 通过递归和回溯，代码枚举了所有可能的选择组合。

  • 提前加入子集：

    • 在每次递归调用开始时，直接将当前 path 加入到 ret 中。这是因为 path 在每一层递归中都表示一个有效的子集，无需等到递归终止才加入。

5. 代码的优化空间

  • 如果输入数组 nums 中包含重复元素，这段代码会生成重复的子集。可以通过排序和剪枝来避免重复子集的生成。

  • 可以将 path 改为引用传递，减少拷贝的开销。

6. 代码的复杂度分析

  • 时间复杂度：O(2^n)，其中 n 是 nums 的大小。因为每个元素有两种选择（选或不选），总共有 2^n 个子集。

  • 空间复杂度：O(n)，递归栈的深度为 n。结果存储空间不计入空间复杂度。

7. 代码的改进版本（避免重复子集）

如果输入数组 nums 中包含重复元素，可以通过排序和剪枝来避免生成重复的子集。改进后的代码如下：

class Solution {
    vector<vector<int>> ret;
    vector<int> path;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序，便于剪枝
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        ret.push_back(path); // 将当前子集加入结果
        for (int i = pos; i < nums.size(); i++) {
            if (i > pos && nums[i] == nums[i - 1]) continue; // 剪枝，避免重复
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back(); // 回溯
        }
    }
};
改进点：

  1. 排序：先对 nums 排序，使得相同的元素相邻。

  2. 剪枝：在递归过程中，如果当前元素和前一个元素相同，并且不是第一次遇到该元素，则跳过，避免重复子集。

8. 总结

        这段代码通过深度优先搜索和回溯的思想，实现了求解数组的所有子集。与解法一相比，解法二的代码更加简洁，直接通过循环和递归来生成所有子集。如果输入数组包含重复元素，可以通过排序和剪枝来优化，避免生成重复子集。代码的核心思想是对每个元素的选择和不选择进行枚举，并通过回溯撤销选择以尝试其他可能性。

重点：

递归的本质

        递归是一种通过函数调用自身来解决问题的编程技巧。在递归过程中，问题的规模会逐渐减小，直到达到一个终止条件。递归的核心思想是分治，即将一个大问题分解为若干个小问题，然后分别解决这些小问题。

在子集问题中，递归的作用是对每个元素做出决策（选或不选），从而生成所有可能的子集。

为什么解法一不需要 for 循环？

在解法一中，递归的逻辑是对每个元素做出“选”或“不选”的决策。具体来说：

  1. 对于当前元素 nums[pos]，有两种选择：

    • 选择它：将其加入 path，然后递归处理下一个元素（pos + 1）。

    • 不选择它：直接递归处理下一个元素（pos + 1）。

  2. 递归的终止条件是 pos == nums.size()，表示已经处理完所有元素。

这种递归逻辑已经隐含了对所有元素的遍历，因此不需要显式的 for 循环。

为什么解法二需要 for 循环？

在解法二中，递归的逻辑是显式地遍历数组中的元素，依次生成子集。具体来说：

  1. for 循环从 pos 开始遍历数组 nums，表示从当前位置开始选择元素。

  2. 对于每个元素 nums[i]，将其加入 path，然后递归处理下一个元素（i + 1）。

  3. 在递归返回后，通过 path.pop_back() 回溯，恢复现场，尝试下一个元素。

这种递归逻辑通过 for 循环显式地遍历元素，确保每个元素都有机会被选中，并且避免生成重复的子集。

递归和 for 循环的关系

  • 递归的本质是遍历：递归确实可以遍历所有元素，但遍历的方式可以是隐式的（如解法一）或显式的（如解法二）。

  • 是否需要 for 循环：取决于递归的逻辑设计。如果递归的逻辑已经隐含了对所有元素的遍历（如解法一），则不需要 for 循环；如果需要显式地遍历元素（如解法二），则需要 for 循环。

两种解法的对比

特性解法一（无 for 循环）解法二（有 for 循环）
递归逻辑对每个元素做出“选”或“不选”的决策显式遍历元素，生成子集
是否需要 for 循环否是
代码结构更简洁更直观
时间复杂度O(2^n)O(2^n)

为什么解法二需要 for 循环？

解法二的递归逻辑是通过 for 循环显式地遍历元素，确保每个元素都有机会被选中，并且避免生成重复的子集。具体来说：

  1. 显式遍历元素：for 循环从 pos 开始遍历数组 nums，表示从当前位置开始选择元素。

  2. 避免重复子集：通过 for 循环从 pos 开始遍历，可以避免生成重复的子集。例如，如果已经选择了 nums[1]，那么后续的子集只能从 nums[2] 开始选择，而不能回头选择 nums[0]。

  3. 生成所有子集：通过 for 循环和递归的结合，确保所有可能的子集都被生成。

总结

  • 递归确实可以遍历所有元素，但遍历的方式可以是隐式的（如解法一）或显式的（如解法二）。

  • 是否需要 for 循环取决于递归的逻辑设计。如果递归的逻辑已经隐含了对所有元素的遍历，则不需要 for 循环；如果需要显式地遍历元素，则需要 for 循环。

  • 解法一和解法二都是正确的，只是它们的递归逻辑和实现方式不同。解法一更简洁，解法二更直观。


http://www.kler.cn/a/566580.html

相关文章：

  • 信刻光盘安全隔离与信息交换系统让“数据摆渡”安全高效
  • vllm源码解析(一)：整体架构与推理代码
  • IDEA - 查看类的继承结构（通过快捷键查看、通过生成类图查看）
  • Git -版本管理工具 -常用API整理
  • 【解决方案】Ubuntu 20.04安装podman和podman-compose
  • 萤石云+DeepSeek，云边融合助力音视频AI新突破
  • 【WPF命令绑定之--没有Command属性的控件如何进行命令绑定？】
  • (学习总结27)Linux工具：软件包管理器 yum、apt 和常用软件包下载安装介绍
  • 【大语言模型笔记进阶一步】提示语设计学习笔记，跳出框架思维，自己构建提示词
  • ＜tauri＞＜rust＞＜GUI＞基于tauri，实现websocket通讯程序（右键菜单、websocket）
  • Unity中协程的使用场景
  • Oracle 基础概念及操作实战
  • 【Prometheus】prometheus服务发现与relabel原理解析与应用实战
  • 前端开发岗模拟面试题C
  • 【算法】双指针2816. 判断子序列
  • k8S通过代理将集群外的中间件引入集群内访问 —— 筑梦之路
  • GCN从理论到实践——基于PyTorch的图卷积网络层实现
  • Jetpack Architecture系列教程之(二)——Lifecycle生命周期感知
  • 【算法 位运算】801. 二进制中1的个数
  • Redis服务安装自启动(Windows版)