面试算法84：包含重复元素集合的全排列

题目

给定一个包含重复数字的集合，请找出它的所有全排列。例如，集合[1，1，2]有3个全排列，分别是[1，1，2]、[1，2，1]和[2，1，1]。

分析

下面采用回溯法的思路来解决这个问题。当处理到全排列的第i个数字时，如果已经将某个值为m的数字交换为排列的第i个数字，那么再遇到其他值为m的数字就跳过。例如，输入nums为[2，1，1]并且处理排列中下标为0的数字时，将第1个数字1和数字2交换之后，就没有必要再将第2个数字1和数字2交换。在将第1个数字1和数字2交换之后，得到[1，2，1]，接着处理排列的第2个数字和第3个数字，这样就能生成两个排列，即[1，2，1]和[1，1，2]。

解

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        List<List<Integer>> result = permuteUnique(nums);
        for (List<Integer> item : result) {
            System.out.println(item);
        }
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        helper(nums, 0, result);
        return result;
    }

    private static void helper(int[] nums, int i, List<List<Integer>> result) {
        if (i == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }

            result.add(permutation);
        }
        else {
            Set<Integer> set = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                if (!set.contains(nums[j])) {
                    set.add(nums[j]);

                    swap(nums, i, j);
                    helper(nums, i + 1, result);
                    swap(nums, i, j);
                }
            }
        }
    }

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