穷举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企服之家，中国第一个企服评测及商务社交产业平台。