Java实现n位数字的全排列

当需要对n位数字进行全排列时，我们可以使用递归的方法，将这个问题分解成子问题。

具体的步骤如下：

1. 首先定义一个长度为n的数组nums，用来存放数字1~n;

2. 然后定义一个指针start，初始值为0，表示从数组的第一个元素开始进行排列；

3. 定义一个递归函数permute，函数中传入nums数组、长度len、当前指针start，返回值为void;

4. 在permute函数中，当start等于len时，则表示已经将nums数组中的数字全部排列完毕，直接将nums数组加入结果集中即可；

5. 在permute函数中，使用for循环将当前指针start以及后面的元素进行交换，使得第start个位置能够取到数组中的所有数字；

6. 交换完成后，将指针start向后移动一位，再递归调用permute函数进行下一级排列；

7. 最后再进行一次for循环，将原本交换过的元素换回来，以便接下来的排列。

具体示例如下：

public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    permuteHelper(nums, nums.length, 0, res);
    return res;
}

private static void permuteHelper(int[] nums, int len, int start, List<List<Integer>> res) {
    if (start == len) {
        List<Integer> permutation = new ArrayList<>();
        for (int num : nums) {
            permutation.add(num);
        }
        res.add(permutation);
        return;
    }
    for (int i = start; i < len; i++) {
        // swap nums[i] and nums[start]
        int temp = nums[i];
        nums[i] = nums[start];
        nums[start] = temp;

        permuteHelper(nums, len, start + 1, res);

        // swap nums[i] and nums[start]
        temp = nums[i];
        nums[i] = nums[start];
        nums[start] = temp;
    }
}

示例1：

假设需要对3位数字进行全排列，使用int[]数组来存放数字。初始化时数组为{1,2,3}。

调用上述的permute函数，得到的结果为：

[
 [1, 2, 3],
 [1, 3, 2],
 [2, 1, 3],
 [2, 3, 1],
 [3, 2, 1],
 [3, 1, 2]
]

示例2：

假设需要对4位数字进行全排列，使用int[]数组来存放数字。初始化时数组为{1,2,3,4}。

调用上述的permute函数，得到的结果为：

[
 [1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [1, 4, 3, 2],
 [1, 4, 2, 3],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [2, 3, 1, 4],
 [2, 3, 4, 1],
 [2, 4, 3, 1],
 [2, 4, 1, 3],
 [3, 2, 1, 4],
 [3, 2, 4, 1],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 4, 1, 2],
 [3, 4, 2, 1],
 [4, 2, 3, 1],
 [4, 2, 1, 3],
 [4, 3, 2, 1],
 [4, 3, 1, 2],
 [4, 1, 3, 2],
 [4, 1, 2, 3]
]