通知： 数据结构精品课 已更新到 V2.1，手把手刷二叉树系列课程 上线，第 16 期刷题打卡开始报名。 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： ---- 本文有视频版： 回溯算法框架套路详解 。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。 这篇文章是很久之前的一篇 回溯算法详解 的进阶版，之前那篇不够清楚，就不必看了，看这篇就行。把框架给你讲清楚，你会发现回溯算法问题都是一个套路。 本文解决几个问题： 回溯算法是什么？解决回溯算法相关的问题有什么技巧？如何学习回溯算法？回溯算法代码是否有规律可循？ 其实回溯算法和我们常说的 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是： 回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」，本文就是简单提一下，等你看到后文 图论算法基础 时就能深刻理解这句话的含义了。 废话不多说，直接上回溯算法框架，解决一个回溯问题，实际上就是一个决策树的遍历过程，站在回溯树的一个节点上，你只需要思考 3 个问题： 1、路径：也就是已经做出的选择。 2、选择列表：也就是你当前可以做的选择。 3、结束条件：也就是到达决策树底层，无法再做选择的条件。 如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。 代码方面，回溯算法的框架： 其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」 ，特别简单。 什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！ 力扣第 46 题「 全排列」就是给你输入一个数组 nums ，让你返回这些数字的全排列。 PS：我们这次讨论的全排列问题不包含重复的数字，包含重复数字的扩展场景我在后文 回溯算法秒杀排列组合子集的九种题型 中讲解。 我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n!