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

这篇具有很好参考价值的文章主要介绍了DFS:深搜+回溯+剪枝解决排列、子集问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

                                    创作不易,感谢三连支持!! 

一、全排列I

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:
    //全局变量
    vector<vector<int>> ret;
    vector<int> path;
    bool check[6];
    vector<vector<int>> permute(vector<int>& nums) 
    {
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.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;
            }
        }
    }
};

二、全排列II

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

 方案1:不合法就continue

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[8];
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
       sort(nums.begin(),nums.end());
       dfs(nums);
       return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.size()) {ret.push_back(path);return;}
        //思路1:考虑不合法的选择 continue   思路2:考虑合法的才进dfs
        for(int i=0;i<nums.size();++i)
        {
        if(check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false))  continue;
        path.push_back(nums[i]);
        check[i]=true;
        dfs(nums);//去下一层找
        path.pop_back();
        check[i]=false;
        }
    }
};

方案2:合法才能进循环

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[8];
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
       sort(nums.begin(),nums.end());
       dfs(nums);
       return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.size()) {ret.push_back(path);return;}
        //思路1:考虑不合法的选择 continue   思路2:考虑合法的才进dfs
        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);//去下一层找
        path.pop_back();
        check[i]=false;
        }
        }
    }
};

三、优美的排列

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:  
    //类似全排列,可以交换位置但是不能重复
    int ret=0;
    bool check[16];
    int countArrangement(int n)
    {
       dfs(1,n);
       return ret;
    }

    void dfs(int pos,int n)
    {
        if(pos==n+1) {++ret;return;}
        for(int i=1;i<=n;++i)
        {
            if(check[i]==false&&(i%pos==0||pos%i==0))
            {
                 check[i]=true;
                 dfs(pos+1,n);
                 check[i]=false;
            }
        }
    }
};

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

四、子集I

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

 策略1:决策树以选不选作为参考,结果为叶子节点

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:
    //设置全局变量
    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);
    }
};

策略2:决策树以选几个为参考,结果为全部节点 

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:
    //设置全局变量
    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();         
        }
    }
};

五、子集II

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

 

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(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();
        }
    }
};

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

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
    int sum=0;//记录总和
    int 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];//利用消消乐的性质恢复现场
        }
    }
};

七、字母大小写全排列

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:
    vector<string> ret; //找返回值
    vector<string> letterCasePermutation(string s) 
    {
       dfs(s,0);
       return ret;
    }

    void dfs(string s,int pos)//用传值s 可以直接在原来的s上进行修改
    {
        while(pos<s.size()&&isdigit(s[pos])) ++pos;
        if(pos==s.size()) {ret.push_back(s); return;}
        //变
        s[pos]^=32;  //^=32(空格)可以完成大小写转化!!
        dfs(s,pos+1);
        s[pos]^=32;
        //不变
        dfs(s,pos+1);
    }
};

八、下一个排列

. - 力扣(LeetCode)

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        if(nums.size()==1) return;//如果只有一个数,就没有必要去修改了
      //思路,找尽可能靠右的低位,与一个尽可能小的大数交换 然后再升序后面的剩余元素
      for(int i=nums.size()-2;i>=0;--i)
      {
        if(nums[i]<nums[i+1]) 
        {
           for(int j=nums.size()-1;j>i;--j)
           {
            if(nums[i]<nums[j]) //找到第一个比i大,
            {
                swap(nums[i],nums[j]);
                sort(nums.begin()+i+1,nums.end());//i位置后面的数升序
                return;//此时返回结果
            }
           }
          }
      }
      //如果循环结束都没有找到第一个升序的,说明是全逆序,此时的结果应该是把你直接变成升序
      sort(nums.begin(),nums.end());
    }
};

九、排列序列

. - 力扣(LeetCode)​​​​​​

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝

class Solution {
public:
    string getPermutation(int n, int k) 
    {
      vector<int> factorial(n);//用来统计各个阶乘
      factorial[0]=1;
      for(int i=1;i<n;++i)//统计1——(n-1)!的阶乘
      {
        factorial[i]= factorial[i-1]*i;
      }
      --k;//康托展开 
      vector<int> check(n+1,1);//可选数
      string ret;
      ret.reserve(n);
      for(int i=1;i<=n;++i)
      {
        int order=k/factorial[n-i]+1;//确定了康拖的首位
          for(int j=1;j<=n;++j)//告诉check数组,该位置得是0 不能再选
             {
                order-=check[j];
                if(order==0)
                {
                    ret.push_back(j+'0');
                    check[j]=0;//说明此数被选过
                    break;
                }
             }
             k%=factorial[n-i];//去找下一个数
      }
          return ret;
    }
};

     排列和子集问题就总结到这啦!!回溯有关的题关键就是画树状图,然后根据树状图去思考怎么进行深搜、回溯和剪枝!!

DFS:深搜+回溯+剪枝解决排列、子集问题,递归、搜索与回溯算法总结,算法,深度优先,c++,leetcode,剪枝文章来源地址https://www.toymoban.com/news/detail-853675.html

到了这里,关于DFS:深搜+回溯+剪枝解决排列、子集问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • (3)回溯算法团灭子集、组合、排列问题 -- 元素无重可复选

    回溯算法团灭子集、组合、排列问题 根据元素是否重复和是否可复选,分为以下三种变体: 1、元素无重不可复选 2、元素有重不可复选 3、元素无重可复选 该篇给出第三种情况的代码,另外两种的实现见上方变体链接。

    2024年02月09日
    浏览(31)
  • 穷举&&深搜&&暴搜&&回溯&&剪枝(3)

    一)字母大小写全排列 784. 字母大小写全排列 - 力扣(LeetCode) 1)从每一个字符开始进行枚举,如果枚举的是一个数字字符,直接忽视 如果是字母的话,进行选择是变还是不变 2)当进行遍历到叶子结点的时候,直接将结果存放到ret里面即可 3)相对于是对于这个决策树做一个深度

    2024年02月14日
    浏览(54)
  • 穷举&&深搜&&暴搜&&回溯&&剪枝(4)

    一)单词搜索: 直接在矩阵中依次找到特定字符串 79. 单词搜索 - 力扣(LeetCode) 画出决策树,只需要做一个深度优先遍历: 1)设计dfs函数:只需要关心每一层在做什么即可,从这个节点开始,开始去尝试匹配字符串的下一个字符,就是从某一个位置的字符开始,上下左右下标看看

    2024年02月09日
    浏览(43)
  • 穷举&&深搜&&暴搜&&回溯&&剪枝(2)

    一)电话号码的字母组合 17. 电话号码的字母组合 - 力扣(LeetCode) 1)画出决策树:只是需要对最终的决策树做一个深度优先遍历,在叶子节点收集结果即可 把图画出来,知道每一层在干什么,代码就能写出来了  2)定义全局变量: 1)定义一个哈希表来处理数字和字符串的映射关系

    2024年02月14日
    浏览(44)
  • 【leetcode】深搜、暴搜、回溯、剪枝(C++)3

    leetcode链接 leetcode链接 leetcode链接 leetcode链接

    2024年02月22日
    浏览(36)
  • 递归实现 组合问题+排列问题(DFS)

    目录 递归实现排列型枚举 递归实现排列类型枚举 II  递归实现组合型枚举 递归实现组合型枚举 II 递归实现指数型枚举 递归实现指数型枚举 II 递归不是循环,递归利用了系统栈,只要是函数都会被系统管理。当执行到函数地址入口时就会为函数在系统栈上分配一块内存。当

    2024年02月15日
    浏览(44)
  • 【leetcode】深搜、暴搜、回溯、剪枝(C++)2

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

    2024年02月20日
    浏览(39)
  • 算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/permutations/ 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 6 -10 = nums[i] = 10 nums 中的所有整数 互不相同 思路 这是一个典型的回溯问题,需要在每

    2024年02月21日
    浏览(71)
  • DFS:二叉树的深搜与回溯

    . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode)  . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 思路1:全局path+回溯  思路2:形参path记录路径结果 . - 力扣(LeetCode) 思路1:全局path+回溯 思路2:参数path记录路径结果 

    2024年04月16日
    浏览(57)
  • 递归、搜索与回溯算法(专题二:深搜)

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

    2024年01月20日
    浏览(81)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包