Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].
题目的要求是求所有可能的不重复的排列，因此可以往DFS方向考虑。整体架构与permutations 类似 又由于数组中可能含有重复的数，因此在此题中需要加入某些限制条件和预处理。
为了避免出现重复的排列方案，需要制定一个访问的规则。如 [0 1 1]，规定如果数组中有两个数以上是相等的，并且该数的前一个数没有被访问过则不能访问该数。如 0 1（1） 1（2） 如果第一个1没有被访问则不能访问第二个1。且 一个数被访问过后下次不应该在被访问。
1 public class Solution { 2 public List<List<Integer>> permuteUnique(int[] nums) { 3 List<List<Integer>> result = new ArrayList<>(); 4 if (nums == null || nums.length == 0) { 5 return result; 6 } 7 List<Integer> list = new ArrayList<Integer>(); 8 Arrays.sort(nums); 9 int[] invited = new int[nums.length]; 10 helper(result, list, nums, invited); 11 return result; 12 } 13 14 private void helper(List<List<Integer>> result, List<Integer> list, int[] nums, int[] invited) { 15 if (list.size() == nums.length) { 16 result.add(new ArrayList<Integer>(list)); 17 return; 18 } 19 for (int i = 0; i < nums.length; i++) { 20 if (invited[i] == 1 || i != 0 && (nums[i] == nums[i -1] && invited[i - 1] == 0)) { 21 continue; 22 } 23 invited[i] = 1; 24 list.add(nums[i]); 25 helper(result, list, nums, invited); 26 invited[i] = 0; 27 list.remove(list.size() - 1); 28 } 29 30 } 31 }
原文：http://www.cnblogs.com/FLAGyuri/p/5267193.html