47. Permutations II

The key of the problem is duplicate removal. The solution contains three steps which is simple:

1. Sort the given array;
2. Use an boolean array used to record whether the element with corresponding element has been used;
3. Judge whether current element is equal to previous element (nums[i] == nums[i - 1]) and previous element is used or not (used[i - 1]).

public void traverse(List<List<Integer>> resultList, List<Integer> current, int[] nums, boolean[] used) {
    if( current.size() == nums.length )
	resultList.add(new ArrayList<Integer>(current));
    else{
	for(int i = 0; i < nums.length; i++) {
	    if( used[i] || ( i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) )
		continue;
	    current.add(nums[i]);
	    used[i] = true;
	    traverse(resultList, current, nums, used);
	    used[i] = false;
	    current.remove(current.size() - 1);
	}
    }
}

public List<List<Integer>> permuteUnique(int[] nums) {
	Arrays.sort(nums);
	List<List<Integer>> resultList = new ArrayList<List<Integer>>();
	traverse(resultList, new ArrayList<Integer>(), nums, new boolean[nums.length]);
	return resultList;
}