如果把深度优先搜索比作一个人的话，那么这个人是一个执着的人，甚至倔强，不把一条路走到底不会返回(回溯)，虽然执着倔强，但是他不傻，如果在探索的途中发现这条路走下去没有希望他会提前返回(剪枝)，不会走到底再返回。

DFS最重要的是顺序，能不重不漏的搜索到每一个节点

深度优先搜索的数据结构为栈(stack）

深度优先搜索的两个注意事项：

小技巧：

每一个DFS都有一棵与之对应的递归搜索树，我们可以借助画图来帮我们理清思路

深度优先遍历图的方法是，从图中某顶点v出发： （1）访问顶点v； （2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式 一个整数 n。

输出格式 按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围 1≤n≤9 输入样例：

输出样例：

题目分析： 当要求字典序的时候，我们从小到大枚举每个数，结果就是字典序。这里我们从位置的角度来思考问题，每个位置应该放哪些数。当第一个位置放1时…,放2时…,放3时…。

具体步骤可参考本专栏另外一篇文章：递归