问题描述：给定一个数组，数组里面有重复元素，求全排列。
算法分析：和上一道题一样，只不过要去重。
3 import java.util.ArrayList; 4 import java.util.HashSet; 5 import java.util.List; 6 import java.util.Set; 7 8 public class PermutationsUnique { 9 public ArrayList > permuteUnique(int[] num) {10 ArrayList > result = new ArrayList >();11 permuteUnique(num, 0, result);12 return result;13 }14 15 private void permuteUnique(int[] num, int start, ArrayList > result) {16 17 if (start >= num.length ) {18 ArrayList item = convertArrayToList(num);19 result.add(item);20 }21 22 for (int j = start; j < num.length; j++) {23 if (containsDuplicate(num, start, j)) {24 swap(num, start, j);25 permuteUnique(num, start + 1, result);26 swap(num, start, j);27 }28 }29 }30 31 private ArrayList convertArrayToList(int[] num) {32 ArrayList item = new ArrayList ();33 for (int h = 0; h < num.length; h++) {34 item.add(num[h]);35 }36 return item;37 }38 //nums[start]和nums[end]交换，如果start-end之间有nums[i]==nums[end],那说明它以前交换过，就不用重复了。39 private boolean containsDuplicate(int[] arr, int start, int end) {40 for (int i = start; i < end; i++) {41 if (arr[i] == arr[end]) {42 return false;43 }44 }45 return true;46 }47 48 private void swap(int[] a, int i, int j) {49 int temp = a[i];50 a[i] = a[j];51 a[j] = temp;52 }53 54 55 56 57 //这种方法和Permutation一样，因为用set了，所以就已经去重了。58 public static List > permuteUnique2(int[] num) {59 List > returnList = new ArrayList<>();60 returnList.add(new ArrayList ());61 62 for (int i = 0; i < num.length; i++) {63 Set > currentSet = new HashSet<>();64 for (List l : returnList) {65 for (int j = 0; j < l.size() + 1; j++) {66 l.add(j, num[i]);67 ArrayList T = new ArrayList (l);68 l.remove(j);69 currentSet.add(T);70 }71 }72 returnList = new ArrayList<>(currentSet);73 }74 75 return returnList;76 }77 78 public static void main(String[] args)79 {80 Permutations pt = new Permutations();81 int[] num = {1,2,1,3};82 System.out.println(pt.permute(num).size());83 System.out.println(pt.permute(num));84 }85 }