想要精通算法和SQL的成长之路 - 全排列

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 全排列

原题连接
给定一个不含重复数字的数组 nums ，返回所有可能的全排列 。

示例 1：

• 输入：nums = [1,2,3]
• 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

public class Test46 {
	// 结果集
    ArrayList res = new ArrayList<ArrayList<Integer>>();

    public List<List<Integer>> permute(int[] nums) {
        // 判空
        if (nums == null || nums.length == 0) {
            return res;
        }
        // 开始递归
        backtrack(new ArrayList<>(),nums);
        return res;
    }

    public void backtrack(ArrayList<Integer> path, int[] nums) {
    	// 如果当前的集合已经满足了元素个数，加入到结果集中，并返回
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 每次遍历都得从0开始，因为是全排列，而不是组合
        for (int index = 0; index < nums.length; index++) {
        	// 因为每次遍历都是从头开始，可能会有重复的情况，这里判断是否使用过该元素
            if(path.contains(nums[index])){
                continue;
            }
            // 当前元素计入结果中
            path.add(nums[index]);
            // 下一层递归
            backtrack(path,nums);
            // 回溯
            path.remove(path.size()-1);
        }
    }
}
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
35

上面的方法中，使用List中自带的contains函数来判断元素的重复使用情况。当然，我们也可以用一个used数组来判断某个元素是否使用过，这样看起来可能更直观点。

public class Test46 {
	// 结果集
    ArrayList res = new ArrayList<ArrayList<Integer>>();
	boolean[] used = null;
	
    public List<List<Integer>> permute(int[] nums) {
        // 判空
        if (nums == null || nums.length == 0) {
            return res;
        }
        // 开始递归
        used = new boolean[nums.length];
        backtrack(new ArrayList<>(),nums);
        return res;
    }

    public void backtrack(ArrayList<Integer> path, int[] nums) {
    	// 如果当前的集合已经满足了元素个数，加入到结果集中，并返回
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 每次遍历都得从0开始，因为是全排列，而不是组合
        for (int index = 0; index < nums.length; index++) {
        	// 因为每次遍历都是从头开始，可能会有重复的情况，这里判断是否使用过该元素
            if (used[index]) {
                continue;
            }
            // 当前元素计入结果中
            path.add(nums[index]);
            // 表示当前元素使用过
            used[index] = true;
            // 下一层递归
            backtrack(path,nums);
            // 回溯
            used[index] = false;
            path.remove(path.size()-1);
        }
    }
}
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
35
36
37
38
39
40

二. 全排列 ||

原题连接
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

• 输入：nums = [1,1,2]
• 输出：[[1,1,2], [1,2,1], [2,1,1]]

在第一题的基础上，多了一个条件：可包含重复数字。那么我们在代码当中，就需要加一个特判：

• 在两个连续的相同数字之间，要做到去重。也可以说剪枝。

不过剪枝的前提是：数组是有序的。因此我们需要对数组进行一个排序。

Arrays.sort(nums);
1

排序之后，我们就需要在代码里的循环体中增加一个特判：判断连续的两个元素是否相同（上一个元素还被使用过）。

if (index > 0 && nums[index] == nums[index - 1] && used[index - 1]) {
	continue;
}
1
2
3

那么完整代码就是：

public class Test47 {
    ArrayList res = new ArrayList<ArrayList<Integer>>();
    boolean[] used = null;

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 判空
        if (nums == null || nums.length == 0) {
            return res;
        }
        used = new boolean[nums.length];
        // 排序，方便剪枝
        Arrays.sort(nums);
        backtrack(new ArrayList<>(), nums);
        return res;
    }

    public void backtrack(ArrayList<Integer> path, int[] nums) {
    	// 找到满足的集合，加入结果集
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int index = 0; index < nums.length; index++) {
        	// 老逻辑，避免同一个元素的重复使用
            if (used[index]) {
                continue;
            }
            // 新逻辑，两个元素虽然不是同一个，但是他们值相同，这里做的是去重
            if (index > 0 && nums[index] == nums[index - 1] && used[index - 1]) {
                continue;
            }
            // 深层递归以及回溯
            path.add(nums[index]);
            used[index] = true;
            backtrack(path, nums);
            used[index] = false;
            path.remove(path.size() - 1);
        }
    }
}
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
35
36
37
38
39
40