題目描述

Given a collection of distinct integers, return all possible permutations.
給出一個(gè)不重復(fù)的數(shù)字的集合，返回所有可能的排列。

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的方式解決，重要的是在于理解如何組合出來不同的全排列。有兩種思路：
一種是高中數(shù)學(xué)學(xué)過的A33全排列的方法，如下圖所示，從第一個(gè)格子開始依次填空，第一個(gè)空可以填1或2或3，當(dāng)填完第一個(gè)格子后，第二個(gè)格子只剩下兩種選擇，當(dāng)填完第二個(gè)格子后，第三個(gè)格子只剩下一種選擇。

A33依次填空

另一個(gè)種是通過交換的方法來實(shí)現(xiàn)，需要理解這樣一個(gè)概念，設(shè)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樹的每一層負(fù)責(zé)定死全排列的每一位，例如第二層通過數(shù)組元素交換負(fù)責(zé)定死第一位為1或2或3，然后再遞歸到下一層去求后面的全排列。

交換的遞歸過程

代碼實(shí)現(xiàn)

第二種思路的實(shí)現(xiàn)代碼如下。

    /**
     * 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;
    }