题目
给出一个具有重复数字的列表，找出列表所有不同的排列。
样例
给出列表 [1,2,2]，不同的排列有：
Paste_Image.png
代码
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
public List<List<Integer>> permuteUnique(int[] nums) {
ArrayList<List<Integer>> res = new ArrayList<>();
if(nums == null)
return null;
if(nums.length == 0)
{
res.add(new ArrayList<Integer>());
return res;
}
ArrayList<Integer> list = new ArrayList<>();
//先将数组排序，这样相同元素将会出现在一起
Arrays.sort(nums);
int n = nums.length;
int[] visited = new int[n];
for(int i=0;i<n;i++)
visited[i] = 0;//0标识未访问
helper(res, list, visited, nums);
return res;
}
private void helper(ArrayList<List<Integer>> res, ArrayList<Integer> list, int[] visited, int[] nums) {
if(nums.length == list.size()) {
res.add( new ArrayList<Integer>(list));
}
for(int i=0;i<nums.length;i++) {
if(visited[i] == 1 || i!= 0 && (visited[i-1] == 0 && nums[i] == nums[i-1]))
continue;
/*
上面的判断主要是为了去除重复元素影响。
比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，
我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果
当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就
不应该让后面的2使用。
*/
list.add(nums[i]);
visited[i] = 1;
helper(res, list, visited, nums);
list.remove(list.size()-1);
visited[i] = 0;
}
}
}
