全排列II -- LeetCode[37]

【Medium】给定一个可包含重复数字的序列，返回所有不重复的全排列。

举例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

回溯法
关于回溯法的其他题型，看这里

这个问题是 LeetCode 46 的一个变形，在回溯法的基础上增加剪枝，来排除掉重复的case。

根据 LeetCode 46 的两种解法，分别来看，这两个题解如何剪枝。

第一个想法就是按照46的解法，找到所有的解之后，再去去重。可行，但是肯定不是我们想要的。

题解一

public class Solution47 {
    public void backTrace(int[] nums, int[] usedMark, List<List<Integer>> output, LinkedList<Integer> tmp) {
        if (tmp.size() == nums.length) {
            output.add(new LinkedList<Integer>(tmp));
        }

        for (int i = 0; i < nums.length;) {
            if (usedMark[i] == 1){
                i++;
                continue;
            }

            tmp.add(nums[i]);

            usedMark[i] = 1;

            int startIndex = i;
            int endIndex = i;

            while ((endIndex != (nums.length - 1)) && (nums[endIndex + 1] == nums[i])) {
                endIndex++;
            }

            backTrace(nums, usedMark, output, tmp);

            // backtrace
            tmp.remove(tmp.size() - 1);
            usedMark[i] = 0;
            // next index 跳过相同的
            i = endIndex + 1;
        }

    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        List<List<Integer>> output = new LinkedList<List<Integer>>();

        LinkedList<Integer> tmp = new LinkedList<Integer>();

        int[] usedMark = new int[nums.length];

        backTrace(nums, usedMark, output, tmp);
        return output;
    }
}

在之前46题的解法一中，用一个used数组来标识本次回溯是否用过这个元素。但是怎么知道是否重复的用过某一个相同的元素呢？

一种就是在每次固定一个元素之后，用map记录下本轮用的元素，下次循环的时候判断是否用过，这种方法是一个解。

还有一种，也是上文给出的题解使用的。优先把整个数组排序，因为每固定一个数的时候，都是从index=0开始，根据used数组来判断是否被使用了。如果数组是有序的，那么遍历的时候，只需要跳过之后所有和上一个相同的元素，就可以了。

回溯方法依旧不变。

题解二

public class Solution47_2 {
    private void backTrace(List<List<Integer>> output, ArrayList<Integer> data, int start) {
        if (start == data.size()) {
            output.add(new LinkedList<>(data));
        }

        int lastValue = 0;
        for (int i = start; i < data.size(); i++) {
            int value = data.get(i);
            if (i != start && lastValue == value){
                continue;
            }
            lastValue = value;
            // 把所有的值都换到后面去
            for (int j = i; j > start; j--) {
                data.set(j, data.get(j-1));
            }
            data.set(start, value);

            backTrace(output, data, start+1);
            // 把所有的值再换回来
            for (int j = start; j < i; j++) {
                data.set(j, data.get(j+1));
            }
            data.set(i, value);
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        quickSort(nums, 0, nums.length - 1);

        List<List<Integer>> output = new LinkedList<List<Integer>>();

        ArrayList<Integer> data = new ArrayList<>();

        for (int value : nums) {
            data.add(value);
        }

        backTrace(output, data, 0);

        return output;
    }
}

在前一题的基础上，看看如果使用46题的题解二的思路，是否可以解决47题。

在46题的题解二中，其实是利用数组的元素交换来 固定一个元素。每次把固定的元素与当前可选range的第一个元素交换，再在剩余的元素中继续递归 固定下一个元素。也就是说，每次在新一轮固定元素的时候，可选range前的所有元素，均是已被选择固定，不可再选。

那么怎么去重呢？

同样的先使用排序，保证数组有序。

假设有一个数组 a a b c（a<b<c）
第一轮，第一个元素固定了第一个 a，假设后面找到了以第一个a开头的所有的解。
第二轮，回溯到原始序列，根据去重，应该忽略第二个 a，选择b,那么第一个a和b交换，即固定在第一个位置。再假设后面找到了以第二个a开头的所有的解。
第三轮，第一个元素固定了c，交换a,c之后，发现问题来了，c后面的大小顺序乱了…

所以假设，当前的range为 start -> N (N是元素个数)，选择了第 i 个元素作为本轮固定元素。

那么把[start i) 区间的所有元素往后挪一位,把第i个元素放在start上。这样就保证了，下一个固定的range内的所有元素是有序的。

回溯的时候，就把(start i]区间的所有元素往前挪一位，然后把第start个元素放回到第i位。

算法复杂度

题解一：
空间复杂度：不变 O(n)
时间复杂度：根据重复元素的多少，最差 O(n^n)

题解二：
空间复杂度：不变 O(1)
时间复杂度：根据重复元素的多少，最差O(n!)

题解二的时间复杂度，在相同数据下，优于题解一。因为题解二无需遍历已经固定的元素，而题解一需要通过usedMark这个数组来判断是否已被固定

与此题型类似的有: