【递归、搜索与回溯算法】专题三：穷举vs暴搜vs深搜vs回溯vs剪枝

📝前言说明：

• 本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

46. 全排列

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

优质解

思路：

• 画出决策树
  

• 设计代码

  • 全局变量

    • vector<vector<int>> ans：记录答案
    • path：记录路径
    • bool check[]：记录对应下标的数有没有被使用过【用于剪枝】

  • dfs函数

    • 单个节点函数体处理
      • 把数枚举一遍，检查check，如果没有用过，就加入path并设计check，然后继续dfs下一层
    • 细节问题
      • 回溯：1. path的最后一个数删掉；2. check对应的被删数位置设置成false
        • 两种时机：dfs返回前回溯，dfs返回后回溯
      • 剪枝：用check判断，如果用过了就不进入对应的分支
      • 递归出口：遇到叶子节点，直接添加节点。（其实也是 path == nums.size()时

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    bool check[7]; // 因为题目的nums的最大长度为 6 
    void dfs(vector<int>& nums)
    {
        if(path.size() == nums.size())
        {
            ans.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;
            }
        }   
    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        dfs(nums);
        return ans;
    }
};

时间复杂度：O(n * n!)
空间复杂度：O(n * n!)

78. 子集

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

优质解

解法一：

决策树（以第一个数为开始，每层判断 选(√) 或 不选(×)）

dfs函数：

• 全局变量
  • ans记录答案，path记录路径
• 剪枝（无）
• 回溯：删掉path最后一个数（当path不为空的时候）
• 处理单个节点：1. 判断当前节点选不选； 2. dfs下一层

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    
    void dfs(vector<int> & nums, int i) // i 代表选到第几个数了
    {
        if(i == nums.size()) // 表示前 n 个全部选完了
        {
            ans.emplace_back(path);
            return;
        }
        // 选
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        // 恢复现场
        path.pop_back();
        // 不选(不选不用恢复)
        dfs(nums, i + 1);
    }
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(nums, 0);
        return ans;   
    }
};

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

解法二：

• 第 n 层：表示该层的子集中选择的元素的个数
• 下一层枚举的开始位置：上一层的下一个位置
• 每个节点都是一个子集

决策树：

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    
    void dfs(vector<int> & nums, int pos)
    {
        ans.emplace_back(path); // 空集一开始就被加进来了
        for(int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(nums, 0);
        return ans;   
    }
};

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！