算法日记：穷举vs暴搜vs深搜vs回溯vs剪枝--全排列

🎬 胖咕噜的稞达鸭：个人主页

全排列：

全排列

算法原理：

穷举–枚举

两数之和->两层 for 循环

1. 画出决策树：
   

2. 设计代码
   用一个全局变量：int[][]ret;来记录最终的结果；int[] path;对决策树进行深度优先遍历的时候记录一下路径；bool[]check;判断这条路径中此时这个位置的数字是否被使用过了，没有用过就添加进path,用check来实现剪枝。
   dfs函数：仅需关心某一个节点在干什么事情。
   细节问题：
   回溯：向上走的时候，干掉path的最后一个元素；修改check数组。
   剪枝：
   递归出口：遇到叶子节点的时候直接添加结果。

3. 代码直译：

classSolution{vector<vector<int>>ret;//返回最后的结果vector<int>path;//记录路径boolcheck[7];//标记这个位置是否使用过，数组的下标public:vector<vector<int>>permute(vector<int>&nums){dfs(nums);//深度优先遍历returnret;}voiddfs(vector<int>&nums){if(nums.size()==path.size())// 终止条件：当前路径长度等于数组长度 → 找到一个完整排列{ret.push_back(path);//插入到ret返回数组中return;}for(inti=0;i<nums.size();i++){if(check[i]==false)//数字还没有用过，check数组表示元素有没有被使用过{path.push_back(nums[i]);//没有使用过插入到数组中check[i]=true;//标记为插入过了dfs(nums);//回溯--->恢复现场path.pop_back();//弹出check[i]=false;//标记为没插入，等下一轮}}}};

全排列二：

全排列II

这道题比上一道题多了一个剪枝的操作。

1. 同一个节点的所有分支中，相同的元素只能选择一次。
2. 同一个数只能使用一次—>check
3. 只关心“不合法”的分支：

check[i]==true||((i!=0)&&nums[i]==nums[i -1]&&check[i]==fasle);

第一种不合法的情况：

(check[i]==true)i这个数字在之前已经使用过了

第二种不合法的情况：

(nums[i]==nums[i-1])而且 第二个同样的数字又出现了(check[i]==fasle;),

这个数字还不能是数组第一个元素(i != 0)处理[1,1,2,1]，[1,2,1,3,1]这种数组，第二个1已经出现过了，第一次要剔除两个1留下[1,2]进行广度遍历。所以首先要把数组进行排序。
不合法的条件：

元素已经进去过的；
当前元素等于上一个元素，而且还是 进去过的（也就是说不可以重复进入）

4. 还要只关心“合法”的分支（什么时候才进入dfs中）``

check[i]==false&&(i=0||nums[i]!=nums[i -1]||check[i -1]==true):

就是说合法可以进入路径的元素符合以下条件：

元素没进去过的；
当前元素跟上一个元素不同的；
虽然跟上一个数字相同但是目前元素没进去过的

5. 代码直译：

classSolution{vector<vector<int>>ret;vector<int>path;boolcheck[9];public:vector<vector<int>>permuteUnique(vector<int>&nums){sort(nums.begin(),nums.end());//先排序dfs(nums,0);//从0的位置开始选择returnret;}voiddfs(vector<int>&nums,intpos){if(pos==nums.size()){ret.push_back(path);return;}for(inti=0;i<nums.size();i++){//剪枝//如果位置不合法，我们就直接跳过:已经进去过的；当前元素和上一个相同的 而且 上一个元素也进去过的if(check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false))continue;//位置合法就进去：还没进去过的； 当前元素和上一个元素相同但是上一个元素进去过此时的元素没进去过 ；当前元素不等于上一个元素的//(check[i] == false && check[i - 1] == true || nums[i] != nums[i-1] || i = 0)path.push_back(nums[i]);check[i]=true;dfs(nums,pos+1);path.pop_back();//恢复check[i]=false;}}};