1. Toy模板网首页
  2. > Toy博客

算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一（leetcode真题剖析）

9月前 作者：爱学习的鱼佬 分类：Toy博客 阅读(70) 违法举报

这篇具有很好参考价值的文章主要介绍了算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一（leetcode真题剖析）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一（leetcode真题剖析）,算法沉淀,算法,剪枝,leetcode

01.全排列

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

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

思路
这是一个典型的回溯问题，需要在每个位置上考虑所有可能情况，并确保不出现重复。通过深度优先搜索的方式，不断枚举每个数在当前位置的可能性，然后回溯到上一个状态，直到枚举完所有可能性得到正确的结果。

在这个问题中，可以通过一个递归函数 backtrack 和一个标记数组 visited 来实现全排列。递归函数的核心思想是在当前位置尝试放置每个数字，然后递归到下一层。同时，使用 visited 数组来判断某个数字是否已经在之前的位置出现过，以确保全排列的唯一性。

代码文章来源地址https://www.toymoban.com/news/detail-833830.html

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool cheak[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(!cheak[i]){
                path.push_back(nums[i]);
                cheak[i]=true;
                dfs(nums);
                path.pop_back();
                cheak[i]=false;
            }
        }
    }
};

02.子集

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

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

思路

这里我们我们可以有下面两种写法，我们结合代码解释

代码一

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

这段代码使用深度优先搜索（DFS）的思想。主要过程如下：

  1. 在dfs函数的一开始，将当前子集 path 加入结果集 ret。
  2. 然后使用循环，从当前位置 pos 开始遍历数组 nums。
  3. 对于每个元素，将其加入当前子集 path，然后递归调用 dfs 函数，继续生成包含当前元素的子集。
  4. 递归完成后，回溯，将刚刚加入的元素从当前子集 path 移出，继续循环遍历下一个元素。

这样，通过深度优先搜索，代码逐步生成了包含不同数量元素的所有子集。

代码二

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. 在dfs函数的一开始，检查当前位置 pos 是否等于数组 nums 的大小。如果相等，表示已经处理完所有元素，将当前子集 path 加入结果集 ret，然后返回结束当前 DFS 分支。
  2. 如果当前位置 pos 不等于数组大小，将当前元素加入子集 path，然后递归调用 dfs 函数，继续生成包含当前元素的子集。
  3. 递归完成后，回溯，将刚刚加入的元素从当前子集 path 移出。
  4. 继续递归调用 dfs 函数，生成不包含当前元素的子集。

这样，同样通过深度优先搜索，代码逐步生成了包含不同数量元素的所有子集。这种实现方式在递归的不同阶段进行了两次递归调用，一次是包含当前元素的情况，一次是不包含当前元素的情况。

03.找出所有子集的异或总和再求和

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

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

  • 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

**注意：**在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

提示：

  • 1 <= nums.length <= 12
  • 1 <= nums[i] <= 20

思路

这一题实际上还是和上一题类似的子集问题，只不过我们将存下的数组变为了一个值，进数组变为子集累计异或的值，出临时数组变为异或相同值，也就是删除异或过的数。

代码

class Solution {
    int sum=0,path=0;
public:
    int subsetXORSum(vector<int>& nums) {
        dfs(nums,0);
        return sum;
    }

    void dfs(vector<int>& nums,int pos){
        sum+=path;

        for(int i=pos;i<nums.size();++i){
            path^=nums[i];
            dfs(nums,i+1);
            path^=nums[i];
        }
    }
};
  1. int sum = 0, path = 0;: 这两个类成员变量用于追踪异或和的总和 (sum) 和当前正在生成的子集异或和 (path)。
  2. int subsetXORSum(vector<int>& nums): 这是主函数，用于调用 DFS 函数，并返回最终的异或和结果。
  3. void dfs(vector<int>& nums, int pos): 这是深度优先搜索（DFS）函数，用于递归生成所有子集的异或和。
    • sum += path;: 在每一层递归中，将当前子集的异或和加到总和中。
    • for(int i = pos; i < nums.size(); ++i) {: 循环从当前位置 pos 开始遍历数组 nums。
    • path ^= nums[i];: 将当前元素 nums[i] 异或到当前子集异或和中。
    • dfs(nums, i + 1);: 递归调用 DFS 函数，以 i + 1 为新的起点，生成包含当前元素的子集异或和。
    • path ^= nums[i];: 回溯，将刚刚异或的元素从当前子集异或和中移出，继续循环遍历下一个元素。
  4. 最终，sum 存储了所有子集的异或和总和，该值作为结果返回。

04.全排列 II

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

定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路

这里要考虑全排列，在同一节点的所有组合中，相同的元素只能选择一次，所以这里我们要有一个标记元素是否使用的数组，在后面的主逻辑递归中，有两种写法，第一种是只关心“不合法”分支，第二种是只关心“合法”分支。

代码一

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool cheak[9];
public:
    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(pos==nums.size())
        {
            ret.push_back(path);
            return;
        }

        for(int i=0;i<nums.size();++i){
            if(cheak[i]||(i!=0&&nums[i]==nums[i-1]&&cheak[i-1]==false))
                continue;
            path.push_back(nums[i]);
            cheak[i]=true;
            dfs(nums,pos+1);
            path.pop_back();
            cheak[i]=false;
        }
    }
};

  1. vector<vector<int>> ret;: 用于存储所有的全排列结果。

  2. vector<int> path;: 用于存储当前正在生成的排列。

  3. bool cheak[9];: 一个布尔数组，用于标记在当前生成排列的过程中哪些元素已经被选择。

  4. vector<vector<int>> permuteUnique(vector<int>& nums): 主函数，用于调用 DFS 函数，并返回最终的全排列结果。

  5. sort(nums.begin(), nums.end());: 在开始生成排列之前，先将输入数组排序，以便处理重复元素。

  6. void dfs(vector<int>& nums, int pos): 深度优先搜索函数，递归生成全排列。

    • if(pos == nums.size()): 如果当前位置 pos 等于数组的大小，表示已经处理完所有元素，将当前排列加入结果集。
      • ret.push_back(path);: 将当前排列加入结果集。
      • return;: 返回结束当前 DFS 分支。
    • for(int i = 0; i < nums.size(); ++i): 遍历数组中的每个元素。
      • if(cheak[i] || (i != 0 && nums[i] == nums[i-1] && cheak[i-1] == false)): 如果当前元素已经被选择（cheak[i] 为 true）或者当前元素与前一个元素相同，且前一个元素未被选择，则跳过当前循环。这是为了处理重复元素的情况，确保不会生成重复的排列。
        • continue;: 跳过当前循环，进入下一个循环。
      • path.push_back(nums[i]);: 将当前元素加入排列。
      • cheak[i] = true;: 将当前元素标记为已选择。
      • dfs(nums, pos + 1);: 递归调用 DFS 函数，继续生成下一个元素的排列。
      • path.pop_back();: 回溯，将刚刚加入的元素移出排列。
      • cheak[i] = false;: 回溯，将刚刚标记为已选择的元素重新标记为未选择。

    代码二

    class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool cheak[9];
public:
    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(pos==nums.size())
        {
            ret.push_back(path);
            return;
        }

        for(int i=0;i<nums.size();++i){
            if(!cheak[i]&&(i==0||nums[i]!=nums[i-1]||cheak[i-1]==true))
            {
                path.push_back(nums[i]);
                cheak[i]=true;
                dfs(nums,pos+1);
                path.pop_back();
                cheak[i]=false;
            }
        }
    }
};
    1. vector<vector<int>> ret;: 用于存储所有的全排列结果。
    2. vector<int> path;: 用于存储当前正在生成的排列。
    3. bool cheak[9];: 一个布尔数组，用于标记在当前生成排列的过程中哪些元素已经被选择。
    4. vector<vector<int>> permuteUnique(vector<int>& nums): 主函数，用于调用 DFS 函数，并返回最终的全排列结果。
    5. sort(nums.begin(), nums.end());: 在开始生成排列之前，先将输入数组排序，以便处理重复元素。
    6. void dfs(vector<int>& nums, int pos): 深度优先搜索函数，递归生成全排列。
      • if(pos == nums.size()): 如果当前位置 pos 等于数组的大小，表示已经处理完所有元素，将当前排列加入结果集。
        • ret.push_back(path);: 将当前排列加入结果集。
        • return;: 返回结束当前 DFS 分支。
      • for(int i = 0; i < nums.size(); ++i): 遍历数组中的每个元素。
        • if(!cheak[i] && (i == 0 || nums[i] != nums[i-1] || cheak[i-1] == true)): 如果当前元素未被选择且（是第一个元素或者与前一个元素不相同或者前一个元素已被选择），则进入循环。
          • path.push_back(nums[i]);: 将当前元素加入排列。
          • cheak[i] = true;: 将当前元素标记为已选择。
          • dfs(nums, pos + 1);: 递归调用 DFS 函数，继续生成下一个元素的排列。
          • path.pop_back();: 回溯，将刚刚加入的元素移出排列。
          • cheak[i] = false;: 回溯，将刚刚标记为已选择的元素重新标记为未选择。

05.电话号码的字母组合

题目链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

思路

这里比前面的排列组合更为简单，只不过在这里我们需要额外创建一个哈希结构来建立数字和字母的映射关系。

代码

class Solution {
    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()) return ret;
        dfs(digits,0);
        return ret;
    }

    void dfs(string& digits,int pos){
        if(pos==digits.size()){
            ret.push_back(path);
            return;
        }

        for(auto ch:hash[digits[pos]-'0']){
            path+=ch;
            dfs(digits,pos+1);
            path.pop_back();
        }
    }
};
  1. string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs","tuv", "wxyz"};: 数字与对应的字母组合的映射关系，hash[2] 对应 “abc”，hash[3] 对应 “def”，以此类推。
  2. string path;: 用于存储当前正在生成的字母组合。
  3. vector<string> ret;: 用于存储所有的字母组合结果。
  4. vector<string> letterCombinations(string digits): 主函数，用于调用 DFS 函数，并返回最终的字母组合结果。
  5. if(!digits.size()) return ret;: 如果输入的数字序列为空，则直接返回空的结果集。
  6. void dfs(string& digits, int pos): 深度优先搜索函数，递归生成数字序列对应的所有字母组合。
    • if(pos == digits.size()): 如果当前位置 pos 等于数字序列的大小，表示已经处理完所有数字，将当前字母组合加入结果集。
      • ret.push_back(path);: 将当前字母组合加入结果集。
      • return;: 返回结束当前 DFS 分支。
    • for(auto ch : hash[digits[pos] - '0']): 遍历当前数字对应的所有字母。
      • path += ch;: 将当前字母加入字母组合。
      • dfs(digits, pos + 1);: 递归调用 DFS 函数，继续生成下一个数字对应的字母组合。
        )`: 主函数，用于调用 DFS 函数，并返回最终的字母组合结果。
  7. if(!digits.size()) return ret;: 如果输入的数字序列为空，则直接返回空的结果集。
  8. void dfs(string& digits, int pos): 深度优先搜索函数，递归生成数字序列对应的所有字母组合。
    • if(pos == digits.size()): 如果当前位置 pos 等于数字序列的大小，表示已经处理完所有数字，将当前字母组合加入结果集。
      • ret.push_back(path);: 将当前字母组合加入结果集。
      • return;: 返回结束当前 DFS 分支。
    • for(auto ch : hash[digits[pos] - '0']): 遍历当前数字对应的所有字母。
      • path += ch;: 将当前字母加入字母组合。
      • dfs(digits, pos + 1);: 递归调用 DFS 函数，继续生成下一个数字对应的字母组合。
      • path.pop_back();: 回溯，将刚刚加入的字母移出字母组合。

到了这里，关于算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一（leetcode真题剖析）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode】深搜、暴搜、回溯、剪枝（C++）2

    【leetcode】深搜、暴搜、回溯、剪枝（C++）2

    leetcode链接 leetcode链接 leetcode链接 全局变量的超时代码： 原因在于nums的长度最长有20，其2^20次方太大了。但是leetcode居然通过了。 path作为参数的正确代码： leetcode链接 解法一： 解法二： 解法一： 解法二： leetcode链接 leetcode链接 leetcode链接 这里我们着重在剪枝方面上面的

    2024年02月20日
    浏览(39)
  • DFS：深搜+回溯+剪枝解决组合问题

    DFS：深搜+回溯+剪枝解决组合问题

                                                   创作不易，感谢支持!!! . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） 该题和前面是类似的，但是用回溯算法，会超

    2024年04月12日
    浏览(38)
  • DFS：深搜+回溯+剪枝解决排列、子集问题

    DFS：深搜+回溯+剪枝解决排列、子集问题

                                        创作不易，感谢三连支持！！  . - 力扣（LeetCode） . - 力扣（LeetCode）  方案1：不合法就continue 方案2：合法才能进循环 . - 力扣（LeetCode） . - 力扣（LeetCode）  策略1：决策树以选不选作为参考，结果为叶子节点 策略2：决策树以选几个

    2024年04月16日
    浏览(65)
  • DFS：深搜+回溯+剪枝解决矩阵搜索问题

    DFS：深搜+回溯+剪枝解决矩阵搜索问题

                                                   创作不易，感谢三连！！  . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） . - 力扣（LeetCode） 1、矩阵搜索问题经常要用到向量，也就是我们可以通过dx和dy来帮助我们定义方向

    2024年04月17日
    浏览(41)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习（组合、排列、总和问题；C++）

    【算法】递归、回溯、剪枝、dfs 算法题练习（组合、排列、总和问题；C++）

    后面的练习是接着下面链接中的文章所继续的，在对后面的题练习之前，可以先将下面的的文章进行了解👇： 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题（C++） 思路 题意分析 ：要求根据给出的数字，算出合法的括号组成个数。根据题目，我们可以总

    2024年02月22日
    浏览(50)
  • 递归、搜索与回溯算法（专题二：深搜）

    递归、搜索与回溯算法（专题二：深搜）

    往期文章（希望小伙伴们在看这篇文章之前，看一下往期文章） （1）递归、搜索与回溯算法（专题零：解释回溯算法中涉及到的名词）【回溯算法入门必看】-CSDN博客 （2）递归、搜索与回溯算法（专题一：递归）-CSDN博客  深搜是实现递归的一种方式，接下来我们之间从题

    2024年01月20日
    浏览(81)
  • Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

    Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

    1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解， 然后综合各个小问题，得到最终答案。 2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。 3、迭代法(Iterative Method) 无法使用公式一次求解，而需要使用重复结构

    2024年02月08日
    浏览(45)
  • 回溯算法例题(剪枝策略)

    回溯算法例题(剪枝策略)

    链接: 77. 组合 链接: 216. 组合总和 III 链接: 17. 电话号码的字母组合 链接: 39. 组合总和 注：使用剪枝必须对原数组进行排序 链接: 40. 组合总和 II 链接: 131. 分割回文串 链接: 93. 复原 IP 地址 链接: 78. 子集 链接: 90. 子集 II 链接: 46. 全排列 链接: 47. 全排列 II 链接: 51. N 皇后 链接

    2024年02月04日
    浏览(90)
  • 【算法】回溯：与递归，dfs的同质与分别，剪枝与恢复现场的详细理解，n皇后的回溯解法及算法复杂度分析。

    【算法】回溯：与递归，dfs的同质与分别，剪枝与恢复现场的详细理解，n皇后的回溯解法及算法复杂度分析。

    目录 ​编辑 1.什么是回溯 2.关于剪枝 3.关于恢复现场 4.题目：二叉树的所有路径（凸显恢复现场：切实感受回溯与深搜） 问题分析 ①函数设置为：void Dfs(root) ②函数设置为：void Dfs(root,path) 解题思想：使⽤深度优先遍历（DFS）求解。 代码实现 5.N后问题 问题分析 4皇后的放置

    2024年04月16日
    浏览(41)
  • 专题二：二叉树的深搜【递归、搜索、回溯】

    专题二：二叉树的深搜【递归、搜索、回溯】

    深度优先遍历 （DFS，全称为DepthFirstTraversal），是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分⽀，直到⼀条路径上的所有节点都被遍历完毕，然后再回溯到上⼀层，继续找⼀条路遍历。 在⼆叉树中，常⻅的深度优先遍历为：

    2024年02月07日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包