LeetCode 47. Permutations II

Problem

LeetCode 47. Permutations II

1. 题目简述

给出一列有重复的数，找出其所有的全排列。例如：

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

2. 算法思路

back tracking回溯法的经典题目之一，LeetCode 46. Permutations的进阶版，问题在于我们怎么去应对这个重复数字的问题。

如果按照以往的思路，对于这种有重复数字的，我们首先需要对数组进行排序，然后才能更好地去对重复数字进行处理。

那么我们能否还像permutation
1的时候，交换然后再找全排列么？不行的，这种去重方式的核心思想在于后面不会再出现比当前更小的数字，这么说可能有点抽象，我们来看个例子。

我们给出一个排好序的数组[1, 1, 2, 2, 3]，按照如上思路的话：

1. 从第1个数开始，分别和1、2、3、4、5进行替换，然后寻找其后面的全排列；

2. 为了不重复，我们每次（除了首次的自我替换）寻找替换的数字的时候，都要找到和当前不一样的数字为止，例如第1个1，和第2个1就不会进行替换，以此类推；

3. 那么问题会出在哪里呢？当我们需要替换第1个1和末尾的3时，数组变为[3, 1, 2, 2, 1]，然后我们找出[1, 2, 2, 1]的全排列;

4. 按照我们的逻辑，1先和第1个2替换，然后跳过第2个2，然后判断到了第2个1，第2个1和它之前的数字2是不同的，因此我们再次替换，到这里我们就会发现出现了重复，明明1和1不应该再替换的，在这里却被再次替换，所以会多出很多重复。

因此我们去重的方式其实可以更简单一点，用hashset来判断是之前是否和同样的元素交换过就可以了，而且原始数组不需要排序也可以。

回溯法

注意这里去重的方式和subset 2以及combination sum
2的去重方式完全不同，具体原因在上面已经详细描述了，建议自己尝试写一下，这里把错误的代码放在文章末尾，大家有兴趣可以自己debug一下，看看哪里出了问题。

这里我们使用hashset来去重。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList();

        if (nums.length == 0) {
            return res;
        }

        getPermutations(nums, 0, res);

        return res;
    }

    private void getPermutations(int[] nums, int start, List<List<Integer>> res) {
        if (start == nums.length) {
            List<Integer> solution = new ArrayList();
            for (int num : nums) {
                solution.add(num);
            }
            res.add(solution);
            return;
        }

        Set<Integer> set = new HashSet();
        for (int i = start; i < nums.length; i++) {
            // 如果set中成功添加了num，则说明当前数字尚未和该数字交换过
            if (set.add(nums[i])) {
                swap(nums, start, i);
                getPermutations(nums, start + 1, res);
                swap(nums, start, i);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

错误版本的代码，警戒

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList();

        if (nums.length == 0) {
            return res;
        }

        getPermutations(nums, 0, res);

        // debug专用，找重复
        // Set<List<Integer>> set = new HashSet();
        // List<List<Integer>> newRes = new ArrayList();

        // for (List<Integer> solution : res) {
        //     if (!set.add(solution)) {
        //         newRes.add(solution);
        //     }
        // }

       return res;
    }

    private void getPermutations(int[] nums, int start, List<List<Integer>> res) {
        if (start == nums.length) {
            List<Integer> solution = new ArrayList();
            for (int num : nums) {
                solution.add(num);
            }
            res.add(solution);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            //这里的去重不行，有很多重复的case,这种写法对于[1,1,2,2,3]没问题，但是对于[0,0,1,1,2,2,3]有问题，自己可以尝试一下。
            if (i > start && (nums[i] == nums[i - 1] || nums[start] == nums[i])) {
                continue;
            }
            swap(nums, start, i);
            getPermutations(nums, start + 1, res);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}