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

?

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
    	List<List<Integer>> total = new ArrayList<List<Integer>>();
    	if (nums==null) {
    		return total;
    	}
    	Arrays.sort(nums);
    	boolean[] flag = new boolean[nums.length];
    	solve(nums, flag, new ArrayList<Integer>(), total);
    	return total;
    }

	private void solve(int[] nums, boolean[] flag,
			ArrayList<Integer> list, List<List<Integer>> total) {
		if (nums.length == list.size()) {
			total.add(list);
			return;
		}
    	for (int i = 0; i < nums.length; i++) {
    		if (flag[i]) {
    			continue;
    		}
    		if (i>0 && nums[i]==nums[i-1] && !flag[i-1]) {
    			continue;
    		}
    		flag[i] = true;
    		ArrayList<Integer> t = new ArrayList<Integer>(list);
    		t.add(nums[i]);
    		solve(nums, flag, t, total);
    		flag[i] = false;
    	}
	}
}

?

Permutations II

原文：http://hcx2013.iteye.com/blog/2220728