子集和全排列（深度优先遍历）问题

                           欢迎访问杀马特主页：小小杀马特主页呀！

目录

前言：

例题一·全排列：

1.题目介绍：

2.思路汇总：

3.代码解答：

例题二·子集：

题目叙述：

解法一：

1.思路汇总：

2.代码解答：

解法二：

 

1.思路汇总：

2.代码解答：

 

文末小总结： 

---

前言：

本篇采用两道例题来讲解利用枚举元素的方法使用决策树通过递归以及穿插回溯来解答类似此类问题的系列模版操作(涉及全局变量以及引用传参使用需要回溯问题与具体什么时候使用等)。

当我们使用全局变量大都就要手动的回溯了，因为它回归到上一层自己不会改变，这里既可以选择全局变量又可以选择引用传参，但是比如一个递归函数需要使用多个变量，这时候引用传参就麻烦了，故需要我们使用全局变量了，因此视情况而定（本篇我们都使用的是全局变量）。

例题一·全排列：

1.题目介绍：

 欢迎大家来挑战：leetcode原题链接： . - 力扣（LeetCode）

2.思路汇总：

画出决策树，然后令dfs函数能帮我们完成此元素位置（从其上到末的path都放入ret）然后对于这个数组就是要遍历它了，由于我们要定义的path是全局遍历故

要考虑回溯（复原操作）：这里就是我们每次往后递归，不能出现前面的元素，故这里开一个bool类型数组记录一下

（一开始是false，变成true就是已经出现了，故不进行操作继续循环）

终止条件：当path满了（等于nums的size）就返回就行了。

思路：从下标0开始遍历数组，遍历到一个就放入path，记录状态，然后继续下面递归，依次重复，

最后肯定会path等于size然后就放入ret，然后回溯：在上一层完成删除path的back即恢复现场的操作，每一次完成一条路线就往回溯，最后归到第一次for循环到退出。

决策图解：

3.代码解答：

class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7]={false};//如果换成vector的bool类型只能用原数组指针区间初始化void dfs(vector<int>& nums){if(path.size()==nums.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;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}};

例题二·子集：

 本题采取两种解法解答，一种是叶子节点放入ret，另一种就是每当递归到一层，这一层的path就是要存入ret的结果。

题目叙述：

  欢迎大家来挑战：leetcode原题链接：. - 力扣（LeetCode）

解法一：

1.思路汇总：

思路：枚举元素：分为选i位置的数和不选两条路径，然后往下递归，最后决策树相当于叶子节点的数就是我们要推进ret的，这里可以假设dfs递归函数可以帮我们完成从传入

  的pos位置一直走到叶子位置的所有分支路径最后的到叶子节点的path都放入ret，然后在第一次分别传入它的左支和右支就可以了。

  细节：注意传入的pos的位置以及回溯的时候path的变化

 

2.代码解答：

class Solution {
public:vector<vector<int>> ret;vector<int> path;
void dfs(vector<int>& nums,int pos){if(pos==nums.size()){ret.push_back(path);path.pop_back();//回溯return;}//可分为左支不走，右支走：//走pos位置的元素（右支）：path.push_back(nums[pos]);dfs(nums,pos+1);//不走pos位置的元素（左支）：dfs(nums,pos+1);}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}

解法二：

1.思路汇总：

思路：我们遍历数组放入path，并且当递归到下一层遍历的时候就是当前位置的下一个开始，所以循环的第一个是pos位置，结合每次下一层递归结束回到上一层都会把下一层的

  path里面加入的nums[i]删除即回溯，保证了每次每当我们进入一次递归第一个就是子集。 

细节：1·为什么ret添加不在for里面：这样的话最后一次递归完成后无法添加最后一次的结果。

        2·为什么每次递归函数传参是i+1不是pos+1呢:这样的话就会导致递归回来的时候走for里的i++的时候再次传入pos+1，又会进行刚才的递归操作了，不符合预期。

2.代码解答：

  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();}}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}

文末小总结： 

像这种类型的dfs思路就是首先根据题意采取穷举等方法画出决策树，然后根据规则转化成递归代码：终止条件，递归操作，回溯，剪枝的判断，其次就是合理应用全局变量等