【深度优先搜索4】输出全排列

深度优先搜索(dfs)

DFS（深度优先搜索）的核心思想是沿着一条路径深入探索，直到无法继续时回退一步，尝试寻找其他未探索的路径。如果依然无路可走，就再次回退，重复这一过程，直到所有可能的路径都被探索完毕。

递归的思想是通过不断调用自身函数，逐层深入解决问题。当满足终止条件时，停止递归并开始逐层回溯。其原理与深度优先搜索的探索与回溯过程高度一致，因此递归是实现深度优先搜索的常用方法。

我们来看看样例是怎么具体实现的

3

题目描述：

给定一个包含 n 个不同整数的数组 nums，请你使用深度优先搜索（DFS）算法，输出数组中所有可能的排列结果。

排列中的每个元素必须是唯一的，按照字典序的顺序排列

输入：

• 第一行输入一个整数 n（1 ≤ n ≤ 9），表示数组中元素的个数。
• 第二行输入 n 个不同的整数，表示数组 nums 中的元素，数组中的元素均为整数，且满足绝对值不超过 $10^4$。

输出：

输出所有可能的排列，每行输出排列。排列中的数字间用空格隔开。

字典序说明:

对于两个不同的字符串，从左到右逐个比较它们的字符：

• 如果在某个位置上它们的字符不同，则将它们按照位置上的字符的字母顺序进行排序，即较小的字符排在前面，较大的字符排在后面。

• 如果一直比较到其中一个字符串结束，则较短的字符串排在前面；

• 如果两个字符串完全相同，则它们的字典序相同。可以将它们看作是按照字母表的顺序进行排序的。

本道题的把数组每个数字看作一个字符，通过字典序比较。

输入示例：

3
1 2 3

输出示例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1