题目：给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例：

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

这是一个全排列组合的算法！
因为题目已经告诉我们，给定的数字序列没有重复，所以这题的结果个数：

N x (N-1) x (N-2) x .... x 3 x 2 x 1 = N! （即这是一个 N 的阶乘）

从全排列问题开始理解回溯算法（以数组 [1, 2, 3] 的全排列为例）

• 以 11 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；
• 以 22 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
• 以 33 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

总结搜索的方法：
按顺序枚举每一位可能出现的情况，已经选择的数字在当前要选择的数字中不能出现。
按照这种策略搜索就能够做到不重不漏。

这样的思路，可以用一个树形结构表示：

算法总结：

1. 我们可以归类为两组数据：已选择的数据 和 待选择的数据；
2. 初始为：[ | 1, 2, 3 ]；
3. pos = 0时 => [ 1 | 2, 3 ]（即已选择[1]和待选择[2, 3]）；
   • pos + 1 => [1, 2 | 3]（即已选择[1, 2]和待选择[3]）；
     • pos + 2 => [1, 2, 3 | ]
       pos + 3 此时已经等于整个数组的个数，所以完成，加入结果集；回退
   • 固定pos + 1不变，交换 2 与 3，即 [1, 3 | 2]，继续；
     • pos + 2 => [1, 3, 2 | ]
       pos + 3 此时已经等于整个数组的个数，所以完成，加入结果集；回退
   • 已无交换，再回退
4. pos = 0不变，交换 1 与 2，即 [2 | 1, 3]
   ..... 过程同 3.a，3.b
5. pos = 0不变，交换 1 与 3，即 [3 | 2, 1]
   ..... 过程同 3.a，3.b

可以看到，整个过程就是一个不断的回溯的过程！

具体的算法：

public class Main {
    private static List<int[]> lists = new ArrayList<>();

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        DFS(nums, 0);

        for (int[] num : lists) {
            System.out.println(Arrays.toString(num));
        }
    }

    private static void DFS(int[] nums, int pos) {
        if (pos == nums.length) {
            int[] num = new int[nums.length];
            System.arraycopy(out, 0, num, 0, nums.length);
            lists.add(num);
            return;
        }

        // pos 就是 分割线『|』左侧刚加入『被选择的数字』
        for (int i = pos; i < nums.length; i++) {
            // i = pos 时的交换与撤回其实没意义
            // 真正有意义的是 i > pos后
            // 即 1与2换，1与3换
            swap(nums, pos, i); // 先交换（如:1 <-> 2）
            DFS(nums, pos + 1); // 递归（继续选择下一个待选择的数字）
            swap(nums, pos, i); // 再撤回（如:2 <-> 1）
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}