解法一：回溯

和普通的全排列一样，都可以使用回溯法，唯一的区别在于需要处理重复元素之前位置互换带来的冗余。令重复元素之前保持某种固定的顺序是一种解决冗余的思路。

  1. class Solution {
  2.     private List<List<Integer>> ans;
  3.     private boolean[] isVisited;
  5.     public List<List<Integer>> permuteUnique(int[] nums) {
  6.         int n = nums.length;
  7.         ans = new LinkedList<>();
  8.         isVisited = new boolean[n];
  9.         // 排序使得重复元素连在一起
  10.         Arrays.sort(nums);
  11.         Integer[] arr = new Integer[n];
  12.         permute(n, nums, 0, arr);
  13.         return ans;
  14.     }
  16.     private void permute(final int N, final int[] nums, int index, Integer[] arr) {
  17.         if (index == N) {
  18.             List<Integer> list = new ArrayList(N);
  19.             Collections.addAll(list, arr);
  20.             ans.add(list);
  21.             return;
  22.         }
  23.         for (int i = 0; i < N; ++i) {
  24.             if (isVisited[i]) {
  25.                 continue;
  26.             }
  27.             // 对于重复数字, 在全排列中出现的次序必须与原来的顺序保持一致
  28.             // 因此如果原来排在它前面的重复数字还没有被使用, 它也不能加入全排列
  29.             if ((i > 0) && (nums[i] == nums[i - 1]) && (!isVisited[i - 1])) {
  30.                 continue;
  31.             }
  32.             arr[index] = nums[i];
  33.             isVisited[i] = true;
  34.             permute(N, nums, index + 1, arr);
  35.             isVisited[i] = false;
  36.         }
  37.     }
  38. }