DFS算法简介
DFS其实叫深度优先搜索算法，起始它只是一种搜索的方法思路，并没有固定的算法格式。我们通常形容他是一条路走到黑。
事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
举例说明之：下图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C,D），则我们可能得到如下的一个访问过程：A->B->E（没有路了！回溯到A)->C->F->H->G->D（没有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）.简要说明深度优先搜索的特点：每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序（具体做法是创建一个list，然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表)，则我们可以得到所谓的"拓扑排序",即topological sort。
DFS复杂度的分析
DFS算法是一一个递归算法，需要借助一个递归工作栈，故它的空问复杂度为O(V)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。
邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。
邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(V)，要查找整个矩阵，故总的时间度为O(V^2)。
v为图的顶点数，E为边数。
DFS算法的基本思路
深度优先遍历图的方法是，从图中某顶点v出发：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
DFS代码模板（Java版和Python版）
前言：
因为博主也是双语言使用者，但是由于对Java基础的不扎实之前的模板和题解就没有写Java版的。但是我觉得还是要挑战一下自己，因为这样不仅可以帮助的学习Java的小伙伴们，而且还能提升博主自己的Java基础水准（在用Java写算法的时候是真的痛苦5555）。看在博主这么用心的份上大伙来个一键三联吧！！！好了，话不多说直接开始上模板！
排列类型模板
众所周知，在LeetCode上我们经常能看见一些排列的问题，我们就拿全排列来举例吧。
题目：全排列
给定一个不含重复数字的数组nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
从题目中我们能大概的了解题意—就是把一个nums数组中的所有的数拿来进行一个打乱顺序的排序。这种类型的题就是输入DFS中的回溯剪枝问题。而且本题还是面试中的高频题！！！
**思路：**本题就是通过一个递归然后一直给path路径数组添加新的元素。最后如果path数组的长度是等于nums数组的长度，则则需要把path数组添加到我们最终需要返回的数组res里面。而本题的核心就在于剪枝和递归的终止条件问题上面。剪枝是需要在递归时不会让path数组反复把同一个元素添加到里面，而是添加nums数组中不同的元素。而递归的终止条件在上面我们也说过，就是如果路径数组path的长度达到了和nums数组相同的长度时，我们就需要终止其继续递归并把路径数组path添加到结果数组res里面。
欧克，大体的思路就是这样。为了更深入的了解本题，我们可以继续向下看看本题的解决代码。
Java版本：
class Solution { //创建返回的数组res和路径数组path List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> path = new ArrayList<Integer>(); public List<List<Integer>> permute(int[] nums) { //获取nums数组的长度，作为下面的终止条件。 int n = nums.length; //进行一个dfs dfs(n,nums); return res; } //创建一个dfs方法，用来查找不同种的排列顺序。 public void dfs(int n,int[] nums){ //设置终止条件 if(path.size() == n){ //如果达到终止条件就证明path已经得到了一种排序，并把这个添加到res数组里面。 res.add(new ArrayList<Integer>(path)); //终止继续递归！ return ; } //设置for循环来对nums数组得遍历和让path数组对其进行添加新的不同元素 for (int i = 0 ; i < n ; i ++){ //设置一个判断，path路径中已经包含了这个元素，则需要跳过此次循环，如果没有则继续向下递归。 if (path.contains(nums[i])){ continue; } //为path数组提添加新的元素。 path.add(nums[i]); //继续递归 dfs(n , nums); //先删除最后一个元素，重新继续组合新的排序。 path.remove(path.size() - 1); } } }
Python版本：
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: #创建一个返回列表res res = [] #定义一个dfs函数 def dfs(path,nums): #设置判断条件，如果路径列表长度等于nums列表长度则终止递归且把path列表添加到res列表当中。 if len(nums) == len(path): res.append(path[:]) return #进行一个for循环，对路径列表逐一进行添加。 for i in nums: #判断如果nums中某个元素已经在路径列表path当中，则为了避免path列表出现重复的元素。 if i in path: continue #继续递归，且在path列表当中添加新的元素 dfs(path + [i] , nums) #执行dfs函数 dfs([],nums) #返回最后的res列表 return res
**本题小结：**通过上面的思路和代码，我们能也能总结出来dfs方法的一些特点：
dfs需要一直递归到一个终止条件。
在使用路径数组path时我们可以发现，其实path数组就是一个栈的形式，每次都会有入栈和出栈。
递归当中其实就好比一个树，需要不断的剪枝和终止条件。
其实dfs掌握上面的核心特点，在做题的时候我们就能知道大概的思路。因为有些题就是在这个上面稍微做了一个简单的修改，我们只需要掌握核心科技，妈妈就不用担心我不会做dfs类型的题啦。
在做过了全排列这个简单的DFS习题后我们接着再来一个简单的DFS习题吧！
题目： 子集 II
给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
从题目我们大概的能知道：
nums包含重复元素。
解集中不能包含重复的解。
OK，我们做题知道了大题的思路后我们就更容易的下手来完成这个题目了。
思路:
首先我们知道这个nums里面包含有重复的元素，但是题目没有给我们说是不是有序的。所有这个我们首先需要对这个nums数组进行一个排序。我们还知道解集中不让出现重复的解，也就是说如果在nums数组里面有相同的元素一般会有两个相同的解。所有为了去除这个重复的解我们就需要在循环时跳过相同的元素，避免出现相同的结果。
大体思路我们已经分析了，接下来就是对代码的逐一分析。
Java版本：
class Solution { //创建返回结果数组res和路径数组path List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> path = new ArrayList<Integer>(); public List<List<Integer>> subsetsWithDup(int[] nums) { //对数组nums先进行一个排序（因为这样更容易跳过相同的元素） Arrays.sort(nums); //执行dfs方法。 dfs(nums,0); return res; } //创建一个dfs方法。 void dfs(int[] nums,int idx){ //因为需要不同的子集，长度已经不再是添加的必要条件； res.add(new ArrayList<Integer>(path)); //长度是一个终止条件！ if (path.size() == nums.length){ return ; } //每层递归需要缩减一个循环范围，避免重复。 for (int i = idx ; i < nums.length ; i ++){ //用来判断相同元素，如果相同则跳过 if (i > idx && nums[i-1] == nums[i]) continue; //入栈 path.add(nums[i]); //继续递归 dfs(nums,i + 1); //出栈 path.remove(path.size() - 1); } } }
Python版本：
class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: #创建dfs函数。 def dfs(begin,path): #对nums数组进行循环 for i in range(begin,len(nums)): #如果如见相同元素则跳过。 if i>begin and nums[i-1] == nums[i]: continue #入栈 path.append(nums[i]) #把path路径数组添加到res返回数组里面。 res.append(path[:]) #继续递归添加 dfs(i+1,path) #出栈 path.pop() #设置返回数组 res = [] #对nums数组进行一个排序，以便检查出重复的元素。 nums.sort() #对给的nums数组判断里面是否存在元素，如果没有存在元素就直接返回一个空集。 if len(nums) == 0: return [[]] #添加一个空集 res.append([]) #进行一个dfs让res获取里面的数。 dfs(0,[]) #返回数组res，即就是我们所获取的全集。 return res
欧克，上面两题就是一个大概的DFS模板。大家只需要记住DFS核心就是需要递归和一个栈。
接下来还是老规矩——给大家加餐哦！！
