题目

给定一个包含重复数字的集合，请找出它的所有全排列。例如，集合[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;}}
}