ToB企服应用市场:ToB评测及商务社交产业平台

标题: 穷举vs暴搜vs深搜vs回溯vs剪枝 [打印本页]
作者: 冬雨财经    时间: 2024-11-20 18:08
标题: 穷举vs暴搜vs深搜vs回溯vs剪枝
目次

1.全分列
2.子集
方法1 
方法2

1.全分列

. - 力扣（LeetCode）

        做此类标题必须先画出决策树，以决策树为首。后面函数计划，全局变量和细节问题都可以想到哪可以写到哪 。
        首先我们要解决的问题是怎样把每层不需要的数，如第二层第一个中的1，以及这棵树中下一层的1.2，我们可以用一个bool数组来解决。初始值为0，假如已经遍历过则赋为1.
        函数体关注某个节点在干什么。我们先判定是否已经遍历完了，遍历完就向上返回。接着我们通过遍历bool数组来查看没有使用过的数。找到了就把他放入path数组，然后dfs进入下一层寻找。每次dfs函数返回到上一层的时候，说明这次查找已经竣事，我们就要把这一次添加的数pop掉。恢复现场
  1. class Solution {
  2. public:
  3.     vector<vector<int>> ret;
  4.     vector<bool> check;
  5.     vector<int> path;
  6.     int size;
  7.     vector<vector<int>> permute(vector<int>& nums) {
  8.         size = nums.size();
  9.         for(int i = 0; i < size;i++)
  10.         {
  11.             check.push_back(0);
  12.         }
  13.         dfs(nums);
  14.         return ret;
  15.     }
  16.     void dfs(vector<int>& nums)
  17.     {
  18.             if(path.size() == size)
  19.             {
  20.                 ret.push_back(path);
  21.                 return;
  22.             }
  24.             int i;
  25.             for(i = 0; i < size; i++)
  26.             {
  27.                 if(check[i] == 0)
  28.                 {
  29.                     path.push_back(nums[i]);
  30.                     check[i] = 1;
  31.                     dfs(nums);
  32.                     //回溯，恢复现场
  33.                     path.pop_back();
  34.                      check[i] = 0;
  35.                 }
  36.             }
  37.          
  38.     }
  39. };
复制代码
2.子集

. - 力扣（LeetCode）
方法1 

 

        这个方法因为每个节点都是一中环境，全部并没有递归出口，每次进入递归把相应的path加入即可。 使用一个i参数来标明函数从哪个地方开始找。当i == 0 （i为下标）时候它下面的递归有i == 1， i == 2，即最左侧的那种环境，接着因为在第二层的时候k会不断累加，以是只有i == 0和i == i的环境。
  1. class Solution {
  2. public:
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5.     vector<vector<int>> subsets(vector<int>& nums) {
  6.         dfs(nums,0);
  7.         return ret;
  8.     }
  9.     void dfs(vector<int>& nums,int i)
  10.     {
  11.         ret.push_back(path);
  12.         for(int k = i; k < nums.size();k++)
  13.         {
  14.             path.push_back(nums[k]);
  15.             dfs(nums,k+1);
  16.             path.pop_back();
  17.         }
  18.     }
  19. };
复制代码
方法2


        这个方法是比较传统的方法，从前去后的每个数都分选和不选，在叶子节点的时候加入ret，递归出口就是i == nums.size（） 。假如选，dfs后要恢复，假如不选则不需要。
  1. class Solution {
  2. public:
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5.     vector<vector<int>> subsets(vector<int>& nums) {
  6.         dfs(nums,0);
  7.         return ret;
  8.     }
  9.     void dfs(vector<int>& nums,int i)
  10.     {
  11.         if(i == nums.size())
  12.         {
  13.             ret.push_back(path);
  14.              return;
  15.         }
  17.             path.push_back(nums[i]);
  18.             dfs(nums,i+1);
  19.             path.pop_back();
  21.             dfs(nums,i+1);
  22.         
  23.     }
  24. };
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4