题目描述

Given a collection of distinct integers, return all possible permutations.
给出一个不重复的数字的集合，返回所有可能的排列。

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路分析

典型的DFS的方式解决，重要的是在于理解如何组合出来不同的全排列。有两种思路：
一种是高中数学学过的A33全排列的方法，如下图所示，从第一个格子开始依次填空，第一个空可以填1或2或3，当填完第一个格子后，第二个格子只剩下两种选择，当填完第二个格子后，第三个格子只剩下一种选择。

A33依次填空

另一个种是通过交换的方法来实现，需要理解这样一个概念，设123的全排列为permute(1,2,3)，那么

permute(1,2,3) = 1,permute(2,3) + 2,permute(1,3) + 3,permute(1,2)
permute(2,3) = 2,permute(3) + 3,permute(2) = 2,3 + 3,2
...

那么可以得到123的全排列如图，DFS树的每一层负责定死全排列的每一位，例如第二层通过数组元素交换负责定死第一位为1或2或3，然后再递归到下一层去求后面的全排列。

交换的递归过程

代码实现

第二种思路的实现代码如下。

    /**
     * 25 / 25 test cases passed.
     *  Status: Accepted
     *  Runtime: 5 ms
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        recursivePermute(nums, 0, result);
        return result;
    }

    private void recursivePermute(int[] nums, int pos, List<List<Integer>> result) {
        if (pos > nums.length - 1) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                temp.add(nums[i]);
            }
            result.add(temp);
            return;
        }

        for (int i = pos; i < nums.length; i++) {
            swap(nums, pos, i);
            recursivePermute(nums, pos + 1, result);
            swap(nums, pos, i);
        }
    }

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