穷举vs暴搜vs深搜vs回溯vs剪枝_全排列_子集

46. 全排列

   递归解决：一开始选一个数，递归进入下一层再选一个新的数，直到到末了一个数。反会上一层遍历其它数。
  每次递归到叶子节点就找到了一种组合，思绪有了详细怎么实现？
  

  1.怎么记录每条路径？
定义一个全局的path数组记录一条路径的数，再定义一个全局的二维数组re记录每条路径。
  2.怎么判断是否到达叶子节点？
当path.size()==nums.size() 把路径path存入re中 并直接返回
  3.剪枝 每一次都要取差别的数，怎么实现？
  同样定义一个全局的数组check，用它记录数是否被使用过。该数在nums的下标映射在check中判断是否遍历过。
  4.当我们从下层返回到上一层的函数时要进行回溯。
  因为path check是全局的，我们要把path check进行还原。path去到末了一个数字，check把对应下标改为false。
  5.递归出口
  叶子节点 直接返回。(不进行回溯，回到上层函数再回溯。因为不止叶子节点返回时要回溯)

1. class Solution {
2.     vector<vector<int>> re;
3.     vector<int> path;
4.     bool check[7];
5. public:
6.     vector<vector<int>> permute(vector<int>& nums) {
7.         dfs(nums);
8.         return re;
9.     }
10.     void dfs(vector<int>&nums)
11.     {
12.         if(path.size()==nums.size())
13.         {
14.             re.push_back(path);
15.             return;
16.         }
17.         for(int i=0;i<nums.size();i++)
18.         {
19.             if(check[i]==false)
20.             {
21.                 path.push_back(nums[i]);
22.                 check[i]=true;
23.                 dfs(nums);
24.                 //回溯
25.                 path.pop_back();
26.                 check[i]=false;
27.             }
28.         }
29.     }
30. };

复制代码

78. 子集

   方法一：对于每一个数我们都有两种环境 选和不选，把全部环境枚举出来就是效果。
  如许我们就画出了一个二叉树，遍历该二叉树，叶子节点就是效果。
  

  1.我们怎么知道该对哪个数进行选择呢？
  给dfs函数传一个参数，用来标记该对谁人数进行选择。
  2.怎么进行选择？
定义全局path记录，选择就push_back()+递归 不选择就直接递归
  3.回溯
  回到上一层时，恢复现场，path.pop
  4.递归出口
  当我们对末了一个数选择完时，就可以保存效果 并返回

1. class Solution {
2.     vector<vector<int>> re;
3.     vector<int> path;
4.     int n;
6. public:
7.     vector<vector<int>> subsets(vector<int>& nums) {
8.         n = nums.size();
9.         dfs(nums, 0);
10.         return re;
11.     }
12.     void dfs(vector<int>& nums, int i)
13.     {
14.         if (i == n)
15.         {
16.             re.push_back(path);
17.             return;
18.         }
20.         // 1.不选nums[i]
21.         dfs(nums, i + 1);
22.         // 2.选nums[i]
23.         path.push_back(nums[i]);
24.         dfs(nums, i + 1);
25.         // 回溯
26.         path.pop_back();
28.         return;
29.     }
30. };

复制代码

  方法二：方法一是对每一个数进行选大概不选
  方法二就是根据选数的个数来找，选0个数的组合 1个数的组合 2个数的组合...
  选0个数:空集
  选1个数: 1 2 3
  选2个数:12 13 23 
  ...
  当我们选完一个数后，选下一个数时，只能选该数在nums数组后面的数。
  eg.选了2后面只能选3 选了3后面没有数了不能继承选

  1.怎么知道该数后面另有那些数？
传参数pos标记该数在nums数组中的位置，for循环遍历它后面的数
  2.递归出口：
每一次进入dfs函数时，当前的path都是一次效果，存入直接返回。

1. class Solution {
2.     vector<vector<int>> re;
3.     vector<int> path;
4.     int n;
6. public:
7.     vector<vector<int>> subsets(vector<int>& nums) {
8.         n = nums.size();
9.         dfs(nums, 0);
10.         return re;
11.     }
12.     void dfs(vector<int>& nums, int pos)
13.     {
14.         re.push_back(path);
15.         for(int i=pos;i<n;i++)
16.         {
17.             path.push_back(nums[i]);
18.             dfs(nums,i+1);
19.             //回溯
20.             path.pop_back();
21.         }
22.     }
23. };

复制代码

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