代码随想录—回溯 | Aryue的个人博客

type

status

date

slug

summary

🤔 综述

回溯是递归的副产品，有递归就会有回溯。

📝回溯=暴力算法

暴力算法的新名称？

回溯就等于暴力算法，那为什么还专门列出来一个模块来讲解呢？

因为有很多题目，用常规的暴力算法就很难解决，比如以下题目：

要在n个数中求k个数的组合，最容易想到的是使用嵌套的for循环来输出，但这样会有问题。要求k个数的组合，就需要k层for循环。我们该如何在代码中编写一个k层的for循环呢？这表明，有些问题使用常规的暴力算法很难解决，因此必须使用回溯算法！

回溯算法

三部曲

递归有三部曲，回溯也有三部曲，可以总结为以下模板：

按照这个模板，可以解决回溯部分大部分的题目。

回溯是一棵树

以组合问题为例，我们可以画一棵树进行分析，这样思路就清晰多了。在解决回溯问题时，如果遇到困难，首先要想到的就是画这棵树！这棵树不仅可以分析题目，对于后续的剪枝优化也有很大帮助。

常见题目类型

组合问题

可以清楚地看出，for循环横向遍历，递归纵向遍历，回溯不断调整结果集。整个回溯系列的核心思路如此，Carl总结得非常好。

优化回溯算法只有剪枝一种方法，比如组合问题优化思路如下：

可以看到，如果要求k=4的组合，如果后续取的数已经不够用了，就可以剪枝了。

组合总和

这部分的题目在基础组合问题基础上增加了一些变化。例如，求总和为sum的组合，或者允许集合中元素的无限制使用。这些变化也反映在代码中，终止条件可能会改变，需要传递额外参数计算总和的sum和最终要求的数target，除此之外没有其他区别。

有些问题可能需要在集合中每个数字只使用一次的前提下进行，但集合中可能存在重复元素。在这种情况下，通常可以先对数组进行排序，以过滤掉一些情况。这也是一种剪枝方法，只不过去重的角度不同。

切割问题

只要能画出树来，思路基本就已经理顺了。

子集问题

子集问题和组合问题是类似的，只不过子集问题要收集所有节点，而组合问题只收集最后的叶子节点。以下是子集问题的树：

排列问题

排列问题又是一种新花样，不过在代码上体现的知识每层从0开始而不是startIndex开始。

N皇后和数独问题

两道困难题，如果与回溯基本思想联系起来的话，其实也达不到困难级别。不过回溯部分的基础题目都是中等难度，所以这些只能算困难！

这部分那就不再用过多篇幅描述了，列出回溯树就能很快理清楚思路。

N皇后的回溯树：

数独问题的回溯树：

性能分析

转载至Carl代码随想录：

关于回溯算法的复杂度分析在网上的资料鱼龙混杂，一些所谓的经典面试书籍不讲回溯算法，算法书籍对这块也避而不谈，感觉就像是算法里模糊的边界。

所以这块就说一说我个人理解，对内容持开放态度，集思广益，欢迎大家来讨论！

以下在计算空间复杂度的时候我都把系统栈（不是数据结构里的栈）所占空间算进去。

子集问题分析：

时间复杂度：O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n)

空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)

排列问题分析：

时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ..... 1 = n!。

空间复杂度：O(n)，和子集问题同理。

组合问题分析：

时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。

空间复杂度：O(n)，和子集问题同理。

N皇后问题分析：

时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * .... * 1。

空间复杂度：O(n)，和子集问题同理。

解数独问题分析：

时间复杂度：O(9^m) , m是'.'的数目。

空间复杂度：O(n^2)，递归的深度是n^2

一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括吧！

🤗总结归纳

继二叉树之后，又啃下了一个大的硬骨头。后续只剩贪心算法和动态规划了！

💡

Written by Aryue,editted by Notion AI.