LeetCode(46) Permutations

发表于 | 更新于 | 分类于

Description:

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

解法：

以A{a,b,c}为例，来说明全排列的生成方法，对于这个集合，其包含3个元素，所有的排列情况有3!=6种，对于每一种排列，其第一个元素有3种选择a,b,c，对于第一个元素为a的排列，其第二个元素有2种选择b,c；第一个元素为b的排列，第二个元素也有2种选择a，c，……，依次类推，我们可以将集合的全排列与一棵多叉树对应。如下图所示

因为没有重复项，可以各位交换模拟选择的过程。在此树中，每一个从树根到叶子节点的路径，就对应了集合A的一个排列。通过递归算法，可以避免多叉树的构建过程，直接生成集合A的全排列，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        get_permutation(nums, 0, nums.length);
        return result;
    }

    void get_permutation(int[] num, int i, int len) {
        if (i == len - 1) {
            List<Integer> tmp = new ArrayList<Integer>();
            for (int j = 0; j < len; j++) {
                tmp.add(num[j]);
            }
            result.add(tmp);
            return;
        }
        for (int j = i; j < len; j++) {
            swap(num, i, j);
            get_permutation(num, i + 1, num.length);
            swap(num, i, j);
        }

    }

    void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

另一种DFS的方法，其实更好理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        int[] used = new int[nums.length];
        List<Integer> tmp = new ArrayList<>();
        dfs(nums, used, tmp);
        return result;
    }

    void dfs(int[] nums, int[] used, List<Integer> tmp) {
        if (tmp.size() == nums.length) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == 1) {
                continue;
            }
            tmp.add(nums[i]);
            used[i] = 1;
            dfs(nums, used, tmp);
            used[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}