Permutations II

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].

与Permutations 这道题不同的是数组中包含重复的元素，有重复的元素我们就不能通过值来判断当前元素是否已经被记录，我们可以通过下标来记录元素是否被记录，因为每个元素的下标是唯一的，这是我们用一个辅助数组isVisited来记录，并且isVisited要同结果集一同回溯。此外数组中可能包含很多重复元素，因此我们可以先将数组排序，然后在回溯时，记录删除的元素，当回溯后继续往前走时，首先判断当前元素与之前删除的元素是否相同，如果相同就直接跳过。代码如下：

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<List<Integer>> llist = new ArrayList<List<Integer>>();
        ArrayList<Integer> isVisited = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return llist;
        java.util.Arrays.sort(nums);
        getPermute(0, nums, isVisited, list, llist);
        return llist;
    }
    public void getPermute(int start, int[] nums, ArrayList<Integer> isVisited, ArrayList<Integer> list, ArrayList<List<Integer>> llist) {
        if(list.size() == nums.length) {
            if(!llist.contains(list))
                llist.add(new ArrayList<Integer>(list));
        }
        int former = Integer.MIN_VALUE;
        for(int i = start; i < nums.length; i++) {
            if(former == nums[i]) continue;
            if(!isVisited.contains(i)) {
                list.add(nums[i]);
                isVisited.add(i);
                getPermute(0, nums, isVisited, list, llist);
                former = list.remove(list.size() - 1);
                isVisited.remove(isVisited.size() - 1);
            }
        }
    }
}