[数据结构与算法]详说深度优先搜索DFS的应用

对于深度优先遍历DFS，通过上一篇《详说广度优先搜索BFS的用法》中提到的DFS的遍历的顺序，不难看出：这个算法会尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。

提到回溯算法，还是会想到深度优先搜索DFS，在我看来在树的深度优先遍历算法（dfs）中，回溯指的就是树遍历的状态重置，和含有递归结构。

对于回溯算法的应用有很多：排列、组合、子集相关问题，我们来通过一些算法应用来更快掌握：

应用一：排列

解题思路：

• 要求返回其所有可能的全排列，先确定第一个数字，之后再往后确定，可以将这个过程看做是一个树的形成过程，整过过程也就是一个树深度优先遍历的思想，也就是回溯。其中还用到了递归。
• 排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），我们需要记录哪些数字已经使用过，因此声明一个boolean类型数组，当值为true时，意味着该数字已经使用过；
• 确定回溯方法的参数：给定的数组，最后返回的列表，遍历存放的列表(会被重置，重置之前内容加入到要返回的列表)，给定的数组的长度，遍历元素的位置，判断是否被选择的boolean类型的数组（标记当前状态）
• 确定递归终止条件：一个排列中的数字已经选够了 ，我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth，表示当前要确定的是某个全排列中下标为 depth的那个数是多少；

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //回溯参数
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int len = nums.length;
        boolean [] used = false;
        if(nums==0){
            return res;
        }
        dfs(nums,res,path,len,0,used[]);
        return res;
    }
    //回溯函数
    dfs(int[]nums,List<List<Integer>> res,List<Integer> path,int len,int depth,boolean[] used){
        if(depth == len){
            // 变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
            // 在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。
            // 这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到空的列表对象。
            // 解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<len;i++){
            if(!used[i]){
                path.add(nums[i]);
                used[i] = true;
            }
            //递归
            dfs(nums,res,path,len,depth+1,used[]);
            //开始回溯（重置）
            used[i] = false;
            path.remove(path.size()-1);
        }
        
    }
}

应用二：组合

解题思路：

• 首先能够脑构出构造树，清楚整个回溯流程；
  根据示例 1：输入: candidates = [2, 3, 6, 7]，target = 7。候选数组里有 2，如果找到了组合总和为 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；同理考虑 3，如果找到了组合总和为 7 - 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。基于以上的想法，可以画出如下构造树

• 组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，为了排除掉重复的，我们在每一次搜索的时候设置 下一轮搜索的起点 begin。

• 思考回溯函数的参数。

• 确定递归终止条件：要找的数的组合 中数小于等于0时，结束此次递归。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int len = candidates.length;
        // boolean[] used = new boolean[len];
        dfs(candidates,res,path,target,0,len);
        return res;
    }
    private void dfs(int[] candidates, List<List<Integer>> res,List<Integer> path,int target,int begin,int len){
       if(target<0){
           return;
       }
       if(target == 0){
           res.add(new ArrayList<>(path));
           return;
       }
       for(int i=begin;i<len;i++){
           path.add(candidates[i]);
           //递归
           dfs(candidates,res,path,target-candidates[i],i,len);
           //回溯（重置）
           path.remove(path.size()-1);
       }

    }
}

总结一下广度优先遍历/搜索应用的步骤：

• 第一步：明确递归参数
• 第二步：明确递归终止条件
• 第三步：明确递归函数中的内容
• 第四步：明确回溯返回值

如果这篇文章对你有帮助的话，就留下一个赞👍吧！