题目描述

46 Permutations:

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]
]

算法1

时间复杂度分析：O(n∗n!)O(n∗n!)，总共n!种情况，每种情况的长度为n

• 枚举每个位置当前放什么数字。used数组标记当前哪些元素被用过了，path数组存储当前枚举的路径，搜索时，依次将每一个没有访问过的元素加入path，修改used标记，递归搜索，然后需要恢复现场。
  

Java 代码 1

class Solution {
    // assume no concurrency
    List<List<Integer>> res = new ArrayList<>();
    // true，那么这个数字nums[i]已经使用过
    boolean[] used = null;
    int n = 0;

    public List<List<Integer>> permute(int[] num) {
        n = num.length;
        if (n == 0) {
            return res;
        }
        used = new boolean[n];
        // 枚举每个位子
        dfs(0, num, new ArrayList<Integer>());
        return res;
    }

    // 枚举每个位置当前可以放什么数字
    private void dfs(int pos, int[] num, ArrayList<Integer> path) {
        // 位子占满
        if (pos == num.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 尝试每个数字加入位子
        for (int i = 0; i < num.length; i++) {
            // true，那么这个数字nums[i]已经使用过
            if (used[i]) {
                continue;
            }

            used[i] = true;
            // 枚举的位子加入尝试的数字
            path.add(pos, num[i]);
            // 枚举下一个位子
            dfs(pos + 1, num, path);
            // 回溯
            used[i] = false;
            // path可以不回溯，以后会被重写覆盖
            path.remove(pos);
        }
    }
}

如下写法也是枚举每个位置可以放哪些数字，只是改写：

Java 代码 2

class Solution {
    // assume no concurrency
    List<List<Integer>> res = new LinkedList<>();
    // 表示i这个数字nums[i]是否已经使用过
    boolean[] used = null;
    int n = 0;

    public List<List<Integer>> permute(int[] num) {
        n = num.length;
        if (n == 0) {
            return res;
        }
        used = new boolean[n];
        dfs(num, new ArrayList<>());
        return res;
    }

    /**
     * 枚举每个位置可以填哪些数字
     * @param num   原数字入参
     * @param path  位置列表
     */
    private void dfs(int[] num, List<Integer> path) {
        if (n == path.size()) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 枚举当前格子可以填写哪些数, 数字全部尝试一遍
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }

            // 当前位置可以加入一个数字
            used[i] = true;
            path.add(num[i]);
            dfs(num, path);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

算法2

时间复杂度分析：O(n∗n!)O(n∗n!)，总共n!种情况，每种情况的长度为n

• 枚举每个数字可以放到哪个位子。used数组元素i为true, 表示这个路径path位置为i的位置path[i]已经使用过了。回溯时候，path可以不回溯，因为以后会被重写覆盖掉。

Java 代码 3

class Solution {
    List<List<Integer>> res = null;
    // true，那么这个位置path[i]已经使用过
    boolean[] used = null;
    int n = 0;

    public List<List<Integer>> permute(int[] num) {
        n = num.length;
        res = new ArrayList<>(n);
        if (n == 0) {
            return res;
        }
        // true，那么这个路径path位置为i的位置，path[i]已经使用过
        used = new boolean[n];

        // path不想使用数组，但是没办法像C++一样vector<int> path(n), Collections.nCopies(n, 0)返回值又是List<Integer>，没法使用ArrayList特性
        ArrayList<Integer> path = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            path.add(0);
        }
        dfs(0, num, path);
        return res;
    }

     /**
     * 枚举每个数字
     * @param currNumIndex 当前枚举数字的下标
     * @param num          原始数组入参
     * @param path         位置列表
     */
    private void dfs(int currNumIndex, int[] num, ArrayList<Integer> path) {
        // 枚举到最后一个数字下标
        if (currNumIndex == num.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 尝试每一个空位置, 用于存放本次枚举的数字
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }

            used[i] = true;
            path.set(i, num[currNumIndex]);
            dfs(currNumIndex + 1, num, path);
            used[i] = false;
            // 可以不用回溯，因为path各个点位置回溯以后会被重写
//            path.remove(i);
        }
    }
}