博客

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]

.

数组中存在重复，不输出重复解

先对原数组排序，然后根据顺序比如[1,1,2]，若第一个1未进入，则第二个1不能进入，要按顺序来，加上标志位flag即可

public class Solution {
     public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
    	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		Arrays.sort(num);
		boolean[] flag = new boolean[num.length];
		dfs(num,0,res,list,flag);
		return res;
    }
	private void dfs(int[] num,int index, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list, boolean[] flag){
		if(index==num.length){
			res.add(new ArrayList<Integer>(list));
			return;
		}
		for(int i=0;i<num.length;i++){
			if(flag[i]||(i>0&&num[i-1]==num[i]&&!flag[i-1]))
				continue;
			list.add(num[i]);
			flag[i]=true;
			dfs(num, index+1, res,list,flag);
			list.remove(list.size()-1);
			flag[i]=false;
		}
	}
}