DFS算法篇：理解递归，熟悉递归，成为递归

在这里插入图片描述

1.DFS原理

那么dfs就是大家熟知的一个深度优先搜索，那么听起来很高大尚的一个名字，但是实际上dfs的本质就是一个递归，而且是一个带路径的递归，那么递归大家一定很熟悉了，大学c语言课程里面就介绍过递归，我们知道就是定义一个函数，然后自己调用自己

那么我们要理解DFS，那么其实就是要理解递归，那么要理解好掌握好递归，那么我们就得明白递归的一个过程，那么递归的一个过程无非就两个字：

”递“和”归“

那么所谓的“递”，那么我们知道要实现递归，就是定义一个函数，然后在该函数内部再调用自己，那么我们知道当执行这个函数体的内的语句的时候，一旦执行到调用该函数本身的语句时，那么我们调用该函数就会为该函数在栈上开辟一份空间，那么开辟的这个空间我们有一个专有名词也就是栈帧来称呼，那么我们会在栈帧中存放该函数体内部所定义的各种局部变量，那么每次调用一个函数我们就会为函数创建一份栈帧，那么这里我们在函数体内部调用了该函数本身，那么这种套娃的行为，程序会为我们调用的该函数又开辟一份空间，只不过这个函数就是本身，然后我们就进入到该函数内部，又重新从函数体开头执行一行一行语句，然后又执行到调用自己的函数语句，又重复我们上述的行为，那么这整个过程，从第一个函数到之后调用自己的函数的一个个过程中，这里就是一个“递”过程，那么我们可以理解第一个函数一直到调用的最后一个函数的关系我们如果用一个层级关系来描述想象的话，那么我们从第一个函数到最后一个函数就是不断往下探索深入的过程，这就是为什么我们要取名为“深度”优先搜索，这里的deep是不是就很形象的描述了递归的一个”递“过程
在这里插入图片描述

而所谓的“归”，那么我们知道我们函数在自己调用自己的时候，我们一定会设置一个终止条件，如果不设置终止条件，那函数会无限的调用自己，反复套娃，而我们刚才说了调用函数会在栈上开辟空间，如果我们反复调用，那么最终会对空间的损耗极其大，所以一旦设置好终止条件之后，也就是我们在函数体内定义的一个return语句，那么我们就会回溯，那么我们上文说了，我们从第一个函数到调用自己创建的最后一个函数的过程，我们可以用层状关系来理解，那么我们结束该调用的函数，那么也就会返回调用我们该函数的上一级函数当中去，那么同理，我们上一级函数调用结束返回也是到调用它的上一级函数当中去，所以我们就这样从底层一直会回溯到顶层的第一个函数，那么第一个函数结束就是回到调用它的main主函数当中去了，那么这就是我们的归过程.

那么在我们知道了我们递归的一个过程，那么我们在理解递归的时候，如果想不通的话就可以通过画图，然后梳理函数之间的调用关系，得到一个层级的图

那么在我们上文中，我描述“递”与“归”过程中举了一个函数自己调用自己的例子来讲解，那么该函数之间的关系就是一个层级关系，但是一旦我们将我们这个例子给修改，也就是我们在一个函数体内部调用我们函数本身的语句不只有一个，而是有多个，那么这种场景就是我们的dfs的情况了

那么此时我们要理解这种场景的话，我们就可以不能用层状关系来描述了，而得是通过树状关系来描述，没错，这个树就是我们学的数据结构的那个树，那么该函数体内有着多个函数调用语句，那么我们就以该函数作为节点，那么其下有多个分支，多个子节点，那么这个子节点就是调用的函数，那么我们执行该递归函数的过程，那么我们可以将其形象的转换为遍历这棵二叉树，假设我们在函数体内部调用该函数本身两次，那么我们执行该递归函数的过程就是从顶部到底部的一个二叉树的前序遍历，也就是先遍历左子树再遍历右子树，而如果我们在该函数体内定义了多个调用函数语句，那么该递归的函数的过程就是遍历一棵多叉树，也是先遍历左子树然后再遍历右侧的子树
那么接下来我有一个问题，读者可以自行思考一下：
那么为什么要我们该递归函数的执行流程转换成多叉树的遍历是前序遍历也就是先遍历左子树再遍历右子树而不是中序或者后序遍历呢？

那是因为我们的递归函数调用，一旦我们执行到该函数调用语句之后，我们会该调用的函数创建一份新的空间，然后就直接进入到该调用函数体的内部，而不会往下执行该调用函数之后的语句，那么也就是在二叉树中最左侧的孩子就是先被调用被创建执行的函数，而右边的函数还没有被调用，也就还没创建出它的空间，所以我们递归的执行只能是一个前序遍历的一个过程
在这里插入图片描述

那么在此模型下，也就是多叉树的遍历模型，我们在加入一个元素那就是我们的DFS了，也就是记录路径信息，那么什么是记录路径信息呢？

我们直到我们DFS的模型就是遍历一棵多叉树，那么该多叉树的第一个节点也就是根节点就是我们的第一个函数，而底部的叶子节点就是我们调用的最后一个函数，那么我们从顶部到达底部的这个路径中，我们沿途通过一个数组或者表等结构来记录我们沿途遍历的各个节点的内容，那么这就是我们的DFS，也就是我开篇所提到的带路径的递归

而不带路径的递归则是我们不记录沿途的各个节点的内容，只是接受节点往上回溯的返回值，例如斐波那契数列，那么这个不带路径的递归，就是我们的动态规划，那么动态规划也可谓是我们算法的一个重量级人物，那么我在后文会更新该内容。

那么彻底知道了我们DFS的一个原理以及模型，那么我们DFS的应用题目就是需要暴力枚举的题目，而大家经常听到的蓝桥杯的暴力方法，也就是本文的主角DFS，

那么我们接下来就看怎么用我们这DFS，那么我在下文准备了几道题目

2.应用

题目一：字符串的全部子序列难度：EZ

题目：现在我们有一个字符串a，我们要得到该字符串的全部子序列。

例：abc的全部子序列有："",“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”

题目思路：那么这里我们要得到该字符串的全部子序列，我们怎么得到我们一个字符串的全部子序列呢，我们就是可以通过枚举每一个位置的两种可能性，也就是该位置的字符在我们的子序列中存在还是不存在，那么我们的一个子序列的确定就是枚举每种位置的这两种可能性然后组合就可以得到我们的子序列，那么我们的枚举过程可以用一个决策树来描述，那么我们每一个位置就是该决策树的一个节点，那么该节点就有两个分支，分别对应我们该位置是否存在在子序列当中还是不存在在子序列当中，那么在每一个分支下有同理也有着两个分支，那么我们这棵决策树就是一棵完全展开的二叉树，那么我们从二叉树的顶部也就是根节点到底部的叶子节点的每一个路径就是我们一个子序列，那么我们就从根节点往下遍历，那么在遍历的过程中同时用一个变量来记录我们遍历的节点的内容，那么一旦到达底部，我们从根节点沿途记录的内容就是我们的其中一个答案

所以只要理解了DFS的一个多叉树遍历模型，那么这题的理解以及DFS的递归的实现就很轻松

代码实现：

class solution
{
	public:
	void dfs(string& a,vector<string>& ans,string temp,int i)
	{
		if(i==a.size())
		{
			ans.push_back(temp);
			return;
		}
		 dfs(a,ans,temp+a[i],i+1)//当前字符存在在子序列中
		 dfs(a,ans,temp,i+1);//当前字符不存在在子序列当中
		 return;
		
	}
	void allsubstring(string& a,vector<string>& ans)
	{
		string temp;
		dfs(a,ans,temp,0);
		return;
	}
}

题目二：字符串的全部不重复的子序列难度：EZ

题目：现在我们有一个字符串a，我们要求该字符串的全部且不重复的子序列

例：abcc的全部不重复子序列："",“a”,“b”,“c”,“ab”,“ac”,“bc”,"“cc”,“abc”,“abcc”

这里的c以及abc会有重复

题目思路：那么这个题我们就得在上一个题的思路下进行一个优化，那么我们知道我们上一个题就是暴力枚举出所有的全部子序列，那么我们这个枚举的过程就是一棵二叉树，我们从顶部到底部进行遍历，而这里我们只不过在添加一个哈希表的结构，然后我们会将从顶部到底部的沿途的所有节点的记录加入到哈希表中去重即可.

代码实现：

class solution
{
	public:
	void dfs(string& a,vector<string>& ans,string temp,int i,unordered_map<string,int>& value)
	{
		if(i==a.size())
		{
			if(value.find(temp)==value.end())
			{
			ans.push_back(temp);
			value[temp]++;
		}
            return ;
		}
		 dfs(a,ans,temp+a[i],i+1)
		 dfs(a,ans,temp,i+1);
		 return;
		
	}
	void allsubstring(string& a,vector<string>& ans)
	{
		string temp;
		unordered_map<string,int> value;
		dfs(a,ans,temp,0,value);
		return;
	}
}

题目三：子集难度：MID

题目:现在有一个数组，那么数组中每个元素可以组成一个集合，请返回所有且不重复的集合。

例：[1,2,3,4]的子集有：[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],

[1,3,4],[2,3,4],[1,2,3,4]

注意：[1,2,3]和[3,2,1]以及[2,1,3]是一个集合

题目思路：那么这里我们解决该题的一个思路还是一个枚举，那么我们按照每个位置是否在这个集合中存在来作为枚举，那么每一个位置都有两种可能，也就是存在在这个集合当中或者不存在在这个集合当中，那么这里我们就枚举每一个位置的可能性，然后每个位置的可能性所组合就是我们的子集了，那么我们枚举的过程就是一棵决策树，那么在当前每个位置的当前所做的决策就是二叉树的一个节点，那么我们现在有两种决策，要么存在在集合中要么不存在在集合中，那么在二叉树的该节点中就对应就会有两个分支，那么同理，这两个分支下有对应着两个分支，那么我们从顶部到达底部的路径的沿途的各个节点组合就是我们的子集，那么我们就遍历我们这棵二叉树，然后我们定义一个变量来记录沿途的路径上的节点内容即可。

class solution
{
	public:
	void dfs(vector<int>& a,vector<vector<int>>& ans,int index,vector<int>& current,unordered_map<string,int>& value)
	{
		if(index==a.size())
		{
			for(int i=0;i<current.size();i++)
			{
				a+=to_string(current[i]);
			}
			if(value.find(a)==value.end())
			{
				ans.push_back(current);
				value[a]++;
			}
			return;
		}
		current.push_back(a[index]);
		dfs(a,ans,index+1,current);
		current.pop_back();
		dfs(a,ans,index+1,current);
		
	}
	void all(vector<int>& a,vector<vector<int>>& ans)
	{
		vector<int> current;
		unordered_map<string,int> value;
		dfs(a,ans,0,current,value);
		return;
	}
}

但是我们可以优化一下，因为我们知道这题存在重复的子集，那么所谓的重复的子集就是集合的各个值的数量一样，但是顺序不一样，那么就是重复的子集，那么我们就可以按照集合的特定的值的数量来进行一个枚举，那么首先我们可以先对数组进行一个排序，这样相同大小的数会在相邻位置，然后我们按照这样的方式来枚举，那么我们枚举集合中值为k的数在集合的数量为0的子集，然后再枚举为值为k数量为1的子集有几个，那么同理对于其他值也是这样，那么我们将每个值在当前集合的数量的可能给组合就是我们的子集，那么按照这样枚举的话我们就能够优化很多重复子集的枚举，实现剪枝

而所谓的剪枝就跟园丁修建树木的花花草草一样，我们这里的剪枝则是要修剪掉重复计算过的分支，这样减少树的遍历从而优化时间复杂度，并且也优化了空间复杂度因为减少了递归函数的调用从而不用为函数创建栈帧，而在上一个题中，我们用哈希表的方式来去重注意那个不是剪枝，我们还是会从树的顶部走到底部，然后将记录的结果加进哈希表中去重，树的分支其实并没有减少

代码实现：

class Solution {
public:
    void dfs(const vector<int>& nums, vector<vector<int>>& subsets, vector<int>& current, int index) {
       if(index==nums.size())
       {
           ans.push_back(current);
           return;
       }

        int i=index+1;
        while(i<nums.size()&&nums[i]==nums[i-1])
        {
            i++;
        }
        for(int j=0;j<i-index;j++)
        {
            current.push_back(nums[index]);
            dfs(nums,subsets.current,i);
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        sort(nums.begin(), nums.end());  // 对数组进行排序
        dfs(nums, result, current, 0);
        return result;
    }
};

题目四：全排列难度：MID

题目：那么现在有一个数组，我们要得到该数组的所有全排列

例：[1,2,3]的全排列有[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]

题目思路：那么这里我们要枚举我们的所有全排列，那么这里我们的枚举思路就是我们假设我们的数组长度为n，那么意味着有n个数，那么我们分别来枚举每一个位置的数的情况，比如第一个位置有n种情况，那么第二个位置有n-1种情况，以此类推，那么我们每个位置的情况组合就得到了我们的全排列，那么我们这个枚举过程就是每一个数的决策就是该多叉树的一个节点，那么我们其中从顶部到底部的各个路径就是我们其中一个全排列，那么我们定义一个变量来记录我们从顶部到达底部的路径沿途的各个节点内容，然后该记录就是我们的一个答案

代码实现：

class solution
{
	public:
	void dfs(vector<int>& a,vector<vector<int>>& ans,vetcor<int>& temp,vector<int>& check)
	{
		if(temp.size()==a.size())
		{
			ans.push_back(temp);
			return;
		}
		for(int i=0;i<a.size();i++)
		{
			if(check[i]==0)
			{
				check[i]=1;
				temp.push_back(a[i]);
				dfs(a,ans,temp,check);
				check[i]=0;
			    temp.pop_back();
			}
		}
		
	}
	void all(vector<int>& a,vector<vector<int>>& ans)
	{
		vector<int> temp;
		vector<int> check(a.size(),0);
		dfs(a,ans,temp,check);
		return;
	}
}

3.结语

那么这就是我们DFS的全部内容，那么我们DFS的应用场景就是那些需要我们去暴力枚举尝试的题目，那么每一次枚举也就是每一次所做的要做的决策就是我们树当中的节点，而其中枚举的可能性就是这个节点所对应的分支，那么我们就沿途遍历这些所有的从顶部到达底部的所有分支，并将沿途的节点内容给记录即可，那么这就是我们的DFS，本质上就是带路径的递归，那么要掌握DFS只要熟悉我们的递归，其实DFS的算法原理与思想其实很简单，挺无脑的，并且知道了DFS的算法模型就是一棵多叉树的话，那么通过递归来实现的难度就减小很多

那么最后感谢你能够耐心的看完本文，那么希望本文能够让你有所收获，我会持续更新，希望你能够多多关注，那么如果我的文章有帮组到你，那还请你多多三连支持哦，你的支持就是我创作的最大的动力！
在这里插入图片描述