算法通过村第十八关-回溯|青铜笔记|什么叫回溯（中篇）-CSDN博客

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

文章目录

前言
回溯的核心问题
撤销操作解释
总结

前言

提示阳光好的时候会感觉还可以活很久甚至可以活出喜悦。 --余秀华

回溯是非常重要的算法思想之一主要解决一些暴力枚举也搞不定的问题这里埋个坑例如组合、分割、子集、棋盘等等。从性能角度来看回溯算法的效率并不是很高但是对于暴力也解决不了的问题它往往很快可以出结果效率低就可以理解了吧。接下来就看看回溯的事情吧

回溯的核心问题

递归+局部枚举+放下前任

接着看这个题目77. 组合 - 力扣LeetCode

当n = 4时我们可以选择的有n有{1234}这四种情况所以我们从第一层到第二层的分支有四个分别表示可取1234.而且这里从左到右取数取过的数不在重复取。第一次取1集合变为234.因为k= 2我们也只能再取1个数就可以了分别取234.得到的集合就是[1,2]、[1,3]、[1,4]。一次类推

横向

在这里插入图片描述
每次从集合中选取元素可选择的范围回逐步收缩到了取4时就直接返为空了。

继续观察树结构可以发现图中每次访问到一个叶子节点图中的标记处我们就可以得到一个结果。虽然到最后时空的但是不影响最终结果。这里相当于从根节点开始每次选择的内容分支达到叶子节点时将其收起起来就是我们想要的结果。

你可以尝试画下n=5k=3的结果有没有感觉

在这里插入图片描述
从图中我们发现元素个数n相当于树的宽度横向而每个结果的元素个数k相当于树的深度纵向。所以我们说回溯问题就是一纵一横而已。在分析我们回发现下面几个规律

我们每次选择都是从类似{1234}{1234}这个样的序列中一个一个选的这就是为什么说是局部枚举后面的枚举范围回越来越小。
枚举时我们就是简单的暴露测试而已一个一个验证能否满足要求从上图可以看到这就是N叉树的遍历过程一次代码相似度很高。
我们再看叶子过程这部分是不是和n = 4k = 2)处理的结果一致也就说是很明显的递归结构。

到此我们还有一个问题待解决就是回溯一般会有一个手动撤销的操作为什么要这么做呢

继续观察纵横图
在这里插入图片描述
我们可以看到我们收集的每个结果不是针对叶子节点的而是针对树枝的比如最上层我们首先确定了1下层我们如果选择了2那么结果就是{12}如果选择了3结果就是{13}.一次类推。现在时怎么确定得到第一个结果时{12}之后,得到第二个结果是{13}呢

继续观察纵横图可以看到我们在得到{12}之后将2撤销再继续使用3就得到了{13}同理也可以得到{1,4},之后这一层就没有了我们可以撤销1继续从最上层取2继续进行。

这里对应的代码操作就是先将第一个结果放在临时列表的Path里面得到第一个结果{12}之后就将path里面的内容放进结果列表resultList中之后将path里面的2撤销掉继续寻找下一个结果{13}继续将path加入resultList中然后再次撤销继续寻找。

现在了解为什么要撤销看图。这个过程我们称它“放下前任继续前进”后面的回溯大都是这样的思路。

这几条就是回溯的基本规律了解这一点我们就可以看看代码是怎么回事了到此我们看看完整的代码时怎样的

 public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <=0 || n < k){
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();

        dfs(n,k,1,path,res);
        return res;
    }

    public void dfs(int n,int k,int startIndex,Deque<Integer> path,List<List<Integer>> res){
        // 递归终止条件path 等于k刚好完成一次
        if (path.size() == k){
            res.add((new ArrayList<>(path)));
            return;
        }
        // 针对每个节点这里就是遍历搜索也就是枚举
        for(int i = startIndex; i <= n; i++){
            // 向路径里添加一个数分支里的取值
            path.addLast(i);
            // 搜索起点要加1就是缩小范围准备下一轮递归这里不允许重复
            dfs(n,k,i + 1,path,res);
            // 递归之后要做同样的逆向操作撤销掉
            path.removeLast();
        }
    }

上面代码还有一个问题需要解释startIndex和i是怎么变化的为什么要传递到下一层+ 1

我们来看看这里的递归循环

   // 针对每个节点这里就是遍历搜索也就是枚举
        for(int i = startIndex; i <= n; i++){
            // 向路径里添加一个数分支里的取值
            path.addLast(i);
            // 搜索起点要加1就是缩小范围准备下一轮递归这里不允许重复
            dfs(n,k,i + 1,path,res);
            // 递归之后要做同样的逆向操作撤销掉
            path.removeLast();
        }

这里的循环有什么作用呢看看这里其实来说是一个枚举第一次n=4可以选择1234四种情况所以就存在4个分支for就需要执行4次
在这里插入图片描述
对于第二层来说第一个数选择1之后身下的元素就只有234了。所以这时候for循环就执行3次后面的只有2次和1次了。

撤销操作解释

如果你还是不清楚的话这里就带图详细的走一遍回溯也就是这个地方有点晕拿下就是胜利✌。

   // 针对每个节点这里就是遍历搜索也就是枚举
        for(int i = startIndex; i <= n; i++){
            // 向路径里添加一个数分支里的取值
            path.addLast(i);
            // 搜索起点要加1就是缩小范围准备下一轮递归这里不允许重复
            dfs(n,k,i + 1,path,res);
            // 递归之后要做同样的逆向操作撤销掉
            path.removeLast();
        }