首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >子集和全排列(深度优先遍历)问题

子集和全排列(深度优先遍历)问题

作者头像
羑悻的小杀马特.
发布于 2025-01-23 09:16:29
发布于 2025-01-23 09:16:29
13100
代码可运行
举报
文章被收录于专栏:杀马特杀马特
运行总次数:0
代码可运行

前言:

本篇采用两道例题来讲解利用枚举元素的方法使用决策树通过递归以及穿插回溯来解答类似此类问题的系列模版操作(涉及全局变量以及引用传参使用需要回溯问题与具体什么时候使用等)。

当我们使用全局变量大都就要手动的回溯了,因为它回归到上一层自己不会改变,这里既可以选择全局变量又可以选择引用传参,但是比如一个递归函数需要使用多个变量,这时候引用传参就麻烦了,故需要我们使用全局变量了,因此视情况而定(本篇我们都使用的是全局变量)。

例题一·全排列:

1.题目介绍:

欢迎大家来挑战:leetcode原题链接: . - 力扣(LeetCode)

2.思路汇总:

画出决策树,然后令dfs函数能帮我们完成此元素位置(从其上到末的path都放入ret)然后对于这个数组就是要遍历它了,由于我们要定义的path是全局遍历故 要考虑回溯(复原操作):这里就是我们每次往后递归,不能出现前面的元素,故这里开一个bool类型数组记录一下 (一开始是false,变成true就是已经出现了,故不进行操作继续循环) 终止条件:当path满了(等于nums的size)就返回就行了。 思路:从下标0开始遍历数组,遍历到一个就放入path,记录状态,然后继续下面递归,依次重复, 最后肯定会path等于size然后就放入ret,然后回溯:在上一层完成删除path的back即恢复现场的操作,每一次完成一条路线就往回溯,最后归到第一次for循环到退出。

决策图解:

3.代码解答:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
     vector<vector<int>> ret;
     vector<int> path;
    bool check[7]={false};//如果换成vector的bool类型只能用原数组指针区间初始化

     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;

            }
        }
     }
    vector<vector<int>> permute(vector<int>& nums) {
          dfs(nums);
       return ret;
    }

};

例题二·子集:

本题采取两种解法解答,一种是叶子节点放入ret,另一种就是每当递归到一层,这一层的path就是要存入ret的结果。

题目叙述:

欢迎大家来挑战:leetcode原题链接:. - 力扣(LeetCode)

解法一:

1.思路汇总:

思路:枚举元素:分为选i位置的数和不选两条路径,然后往下递归,最后决策树相当于叶子节点的数就是我们要推进ret的,这里可以假设dfs递归函数可以帮我们完成从传入 的pos位置一直走到叶子位置的所有分支路径最后的到叶子节点的path都放入ret,然后在第一次分别传入它的左支和右支就可以了。 细节:注意传入的pos的位置以及回溯的时候path的变化

2.代码解答:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:

   vector<vector<int>> ret;
    vector<int> path;
void dfs(vector<int>& nums,int pos){
      if(pos==nums.size()){
         ret.push_back(path);
        path.pop_back();//回溯
         return;
      }
      //可分为左支不走,右支走:

      //走pos位置的元素(右支):
      path.push_back(nums[pos]);
      dfs(nums,pos+1);
      //不走pos位置的元素(左支):
       dfs(nums,pos+1);
        

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

解法二:

1.思路汇总:

思路:我们遍历数组放入path,并且当递归到下一层遍历的时候就是当前位置的下一个开始,所以循环的第一个是pos位置,结合每次下一层递归结束回到上一层都会把下一层的 path里面加入的nums[i]删除即回溯,保证了每次每当我们进入一次递归第一个就是子集。

细节:1·为什么ret添加不在for里面:这样的话最后一次递归完成后无法添加最后一次的结果。 2·为什么每次递归函数传参是i+1不是pos+1呢:这样的话就会导致递归回来的时候走for里的i++的时候再次传入pos+1,又会进行刚才的递归操作了,不符合预期。

2.代码解答:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  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();
          
       }
     
    }
 vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0);
        return ret;
   }

文末小总结:

像这种类型的dfs思路就是首先根据题意采取穷举等方法画出决策树,然后根据规则转化成递归代码:终止条件,递归操作,回溯,剪枝的判断,其次就是合理应用全局变量等

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-10-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【回溯】学会全排列了吗?来看看子集问题!
​ 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
利刃大大
2025/02/02
1030
【回溯】学会全排列了吗?来看看子集问题!
DFS:深搜+回溯+剪枝解决排列、子集问题
排列和子集问题就总结到这啦!!回溯有关的题关键就是画树状图,然后根据树状图去思考怎么进行深搜、回溯和剪枝!!
小陈在拼命
2024/04/04
1510
DFS:深搜+回溯+剪枝解决排列、子集问题
【回溯+剪枝】组合问题!
​ 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
利刃大大
2025/02/02
1060
【回溯+剪枝】组合问题!
DFS:深搜+回溯+剪枝解决组合问题
小陈在拼命
2024/04/09
1430
DFS:深搜+回溯+剪枝解决组合问题
【代码随想录】二刷-回溯算法
回溯算法 ---- 什么是回溯算法? 回溯算法也可以叫做回溯搜索法,它是一种搜索方式。 回溯是递归的副产品,只要有递归就会有回溯。 回溯法的效率: 回溯法的本质是穷举,穷举所有可能,然后选出我们想要的答案。(n层for循环嵌套) 如果想让回溯法更高效一些,可以加一些剪枝操作,但也无法改变回溯法就是穷举的本质。 回溯法一般可以解决如下几种问题: 组合问题: N个数里面按一定规则找出K个数的集合 切割问题: 一个字符串按一定规则由于几种切割方式 子集问题: 一个N个数的集合里有
半生瓜的blog
2023/05/13
9950
【代码随想录】二刷-回溯算法
深度优先搜索(DFS)与回溯法:从全排列到子集问题的决策树与剪枝优化
深度优先搜索(DFS)和回溯法是解决复杂问题中不可或缺的算法工具,尤其在组合问题(如全排列、子集等)中,发挥着至关重要的作用。通过递归的方式,DFS 能够遍历问题的解空间,而回溯法则通过撤销不合法的选择,避免重复计算,提高效率。在解题过程中,剪枝是优化回溯法的重要手段,它通过提前排除无效路径,进一步减少了运算的复杂度。本文将深入探讨如何使用 DFS、回溯法及剪枝技术,构建解决全排列和子集问题的决策树,并优化算法的执行效率。
suye
2024/12/20
3180
深度优先搜索(DFS)与回溯法:从全排列到子集问题的决策树与剪枝优化
【算法学习】递归、搜索与回溯算法(一)
https://blog.csdn.net/2301_80220607/category_12922080.html?spm=1001.2014.3001.5482
GG Bond1
2025/05/06
1410
【算法学习】递归、搜索与回溯算法(一)
【递归与回溯深度解析:经典题解精讲(上篇)】—— LeetCode
解题思路 这是一道典型的 回溯(Backtracking)问题,我们需要枚举所有可能的子集。关键点是每个数字都有两种选择:要么包含,要么不包含。
用户11286421
2025/01/17
3220
【递归与回溯深度解析:经典题解精讲(上篇)】—— LeetCode
【回溯】目标和 && 字母大小全排列
向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :
利刃大大
2025/02/02
670
【回溯】目标和 && 字母大小全排列
数字排列
对于相同数,我们人为定序,就可以避免重复计算:我们在dfs时记录一个额外的状态,记录上一个相同数存放的位置 start,我们在枚举当前数时,只枚举
派大星在吗
2021/12/17
6680
【回溯+剪枝】找出所有子集的异或总和再求和 && 全排列Ⅱ
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果;如果数组为 空 ,则异或总和为 0 。
利刃大大
2025/02/02
1700
【回溯+剪枝】找出所有子集的异或总和再求和 && 全排列Ⅱ
Leetcode题目078-子集
https://leetcode.cn/problems/subsets/solutions/229569/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
用户6021899
2022/11/18
2310
Leetcode题目078-子集
算法妙妙屋-------1.递归的深邃回响:全排列的奇妙组合
全排列(Permutation)是数学中一个经典的问题,指的是从一组元素中,将所有元素按任意顺序排列形成的所有可能序列。
hope kc
2025/06/02
1250
算法妙妙屋-------1.递归的深邃回响:全排列的奇妙组合
【LeetCode 热题 100】全排列 / 子集 / 组合总和 / 分割回文串 / N 皇后
_小羊_
2025/05/15
940
【LeetCode 热题 100】全排列 / 子集 / 组合总和 / 分割回文串 / N 皇后
【回溯+剪枝】回溯算法的概念 && 全排列问题
​ 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
利刃大大
2025/02/03
1750
【回溯+剪枝】回溯算法的概念 && 全排列问题
【递归与回溯深度解析:经典题解精讲(中篇)】—— LeetCode
用户11286421
2025/01/17
1720
【递归与回溯深度解析:经典题解精讲(中篇)】—— LeetCode
【深度优先搜索篇】带你暴力dfs去破解飞机降落和八皇后问题(轻松拿捏版)
通过基于深度优先算法的掌握下;对本篇引入的两道题目如何解答;为什么要这么做而展开的深入探讨,目的在于帮助读者理解这种算法要如何应用;怎么实际解答算法问题。
羑悻的小杀马特.
2025/01/23
890
【深度优先搜索篇】带你暴力dfs去破解飞机降落和八皇后问题(轻松拿捏版)
刷题打卡-子集
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
早起的鸟儿有虫吃
2023/03/21
2230
刷题打卡-子集
【回溯+剪枝】电话号码的字母组合 && 括号生成
​ 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
利刃大大
2025/02/02
900
【回溯+剪枝】电话号码的字母组合 && 括号生成
回溯算法:递增子序列
题目链接:https://leetcode-cn.com/problems/increasing-subsequences/
代码随想录
2020/11/11
1.3K0
回溯算法:递增子序列
推荐阅读
相关推荐
【回溯】学会全排列了吗?来看看子集问题!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档