# 在开始之前
根据我深耕技术写作多年的经验，很多同学一看到标题里有“思想”两个字，就会觉得接下来要讲的一定是一个非常复杂的“高大上”理论，于是他会先给自己箍上一个“我一定学不会”的紧箍咒，接着心里就开始打退堂鼓了。这样的同学在和算法正面交锋之前，就先被自己内心的恐惧击垮了，实在可惜。
站在讲解者的角度来说，我确实不会先给大家画个饼，说这玩意儿有多么多么简单——这是一个非常不负责任的承诺。因为对于初学者来说，没有什么是简单的，从不会到会本来就是一个过程。况且，你现在学的是不少前端er都不肯学/学不动的算法，这本就不是一个轻松的挑战。但既然走到了这一步，不管你这会儿心里有多慌，我都希望你可以坚持一下、读读看，你会发现这玩意儿真的不是玄学——它真的很香。
# 如何学好这一节
不可否认，在一些传统教材里，谈及“思想”必定会有大段理论文字的堆砌，这也是很多同学学完数据结构直接放弃学习算法思想的重要原因。
但站在面试的角度来看，算法相关的考察几乎不存在“背知识点”这种形式，更多还是看你能不能把题做出来。算法思想是抽象的，题目却是具体的。我们常说“以题为纲”，其目的就是帮助大家站在具体去理解抽象。
本节我们先不用纠结什么是递归、什么是回溯，而是直接来做一道题，从题中去认识所谓的“思想”。
通过本节的学习，我希望大家能够认识到，“思想”并不是一坨剪不断理还乱、学了只能用来吹水的虚无概念。“思想”本质上就是套路，而且是普适性非常强的套路，它有着大量的对口问题。搞定了它，就搞定了一大波面试题——爽不爽？要想爽这一把，就不要轻易撤退。
# 关键套路初相见：全排列问题
题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例：
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路分析
“全排列”是高中数学里的一个概念，这里先带大家复习一下：
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
不过就算你已经完全忘了“全排列”到底是一个什么样的数学概念，也没有关系。结合题目描述和示例，我们依然可以分析出这道题想让我们做的事情：拿到一个 n 个数的数组作为入参，穷举出这 n 个数的所有排列方式。
哎？等等，我好像看到一个熟悉的词眼——穷举！楼上是不是说了穷举？我们最近还在哪里见过穷举？是不是在上一节？上一节的哪个位置？DFS 对不对？DFS 用什么实现比较好？递归！好，来得早不如来得巧，我现在就决定用递归来做这个题。
如果你的脑回路暂时没有反应出来上面这些知识点之间的关联关系，也不要着急。新手上路，这很正常。
做完下面一系列的题目之后，我会跟大家介绍这类题目的关键特征，到时候会有更直白的套路可以用。现在先不要慌，跟着我的思路往下走，好好敲代码
怎么做呢？大家仔细想想，在这个变化的序列中，不变的是什么——是不是坑位的数量？拿示例来说，不管我怎么调整数字的顺序，它们都只能围着这 3 个坑打转。当我们感到变化难以把握时，不如尝试先从不变的东西入手。这里我把坑位给大家画出来：
现在问题变成了，我手里有 3 个数，要往这 3 个坑里填，有几种填法？我们一个一个坑来看：
Step1:：面对第一个坑，我有3种选择：填1、填2、填3，随机选择其中一个填进去即可。Step2：面对第二个坑，由于 Step1 中已经分出去1个数字，现在只剩下2个选择：比如如果 Step1 中填进去的是 1，那么现在就剩下2、3；如果 Step1 中填进去的是 2，那么就剩下 1、3。Step3： 面对第三个坑，由于前面已经消耗了2个数字，此时我们手里只剩下 1 个数字了。所以说第 3 个坑是毫无悬念的，它只有1种可能。
我们把三个坑的情况统筹起来，那么全排列就一共有 3x2x1=6 种可能。可惜这道题问的不是全排列的可能性有多少种，而是要求你把每一种可能性都穷举出来。这其实有点类似于我们上一节玩迷宫游戏的时候，游戏规则不仅要求你回答出迷宫的通关方法有几种，还要求你列举出每一条路的路径。列举“路径”，我们首先要找到“坐标”。在这道题里，“坐标”就是每一个坑里可能填进的数字。我把它画出来，你就明白了：
root 是一个空坐标，是我们分配数字的起点。
你可以想象自己此时此刻正手握 3 个数字站在 root 这个位置上。眼前是第一个坑，这个坑向你问道：“小哥，你打算给我哪个数字呢？”
你说：“不好说，这里有 3 种可能”。第一个坑里可以填的数字，对应的是以下三种情况：
接着，你走到了第二个坑。第二个坑问你：“小哥，你打算给我哪个数字呢？”。
你仔细想想，说：“不好说，这要看我给了 1 号坑哪个数字。但可以确定的是，不管我给了 1 号坑哪个数字，到你这里的时候，都只有 2 个数字可选了”。基于 1 号坑的分配结果，2 号坑分别有以下可能：
终于，你走到了第三个坑。此时，你手里只剩下 1 个数，还没等第 3 个坑问你要，你就对它说：“哥，别挑了，我就剩一个了，你没得选”。说着，你把 1 号坑和 2 号坑挑完剩下的最后 1 个数给了 3 号坑
有没有发现，不知不觉中，我们构造出了一个树结构。 从这个树结构里我们可以清晰地看出，全排列的所有可能性：
图中以圆点为起点，以箭头为终点，起点和终点之间就是一个完整的排列。
我们的思维路径是一个树结构，但这并不意味着我们需要真的在编码的时候去构造一棵树出来。回忆一下上一节，我们走迷宫的各种路径组合起来，是不是也是一个树结构？走迷宫时我们没有构造树，这里也不需要构造树。需要什么？需要递归！
即便不联想咱们刚刚学过的 DFS 知识点，这道题的解答思路中也有一个非常关键的特征在提醒你往递归去想，那就是重复。
这里给大家一个思维工具：以后只要分析出重复的逻辑（排除掉类似数组遍历这种简单粗暴的重复），你都需要把递归从你的大脑内存里调度出来、将其列为“可以一试”的解法之一；只要想到递归，立刻回忆我们上一节讲的 DFS 思想、然后尝试套我们这一节末尾教给大家的解题模板。这个脑回路未必 100% 准确，但确实有极高的成功概率——题，是有规律的。这，就是规律之一。
在以上的“填坑”过程中，我们重复地做了以下事情：
- 检查手里剩下的数字有哪些
- 选取其中一个填进当前的坑里
在第 5 节初识递归时，大家已经知道“重复”的内容，就是递归式。
这个重复递归式的动作一直持续到了最后一个数字也被填进坑里为止——“重复”的终点，就是递归边界。
这里大家当然也可以借鉴遍历二叉树的经验 ，通过判断数组的可选数字是否为空，来决定当前是不是走到了递归边界。但是这道题其实可以做得更简单：坑位的个数是已知的，我们可以通过记录当前坑位的索引来判断是否已经走到了边界：比如说示例中有 n 个坑，假如我们把第 1 个坑的索引记为 0 ，那么索引为 n-1 的坑就是递归式的执行终点，索引为 n 的坑（压根不存在）就是递归边界。
递归的编码实现，无非是把我们上面描述过的递归式和递归边界翻译成代码：
编码实现
