学步园

这里我用了递归解法。关键在于如何去重，而去重的关键在于同样的数字，在新的排列中，序号必须总是升序（或者总是降序）。

比如1,1,3

两个1的序号是0,1.

如果是升序的话，只能是1,1,3（序号是0,1,2），不能是1,1,3(序号1,0,2)。

然后在实际编程中，没有必要排序或者用一个数组来记录序号，只是在插入数值num[i]到位置j时候，发现j前面已经有num[i]了，那么就抛弃这个序列，因为j前面有同样数值的话，它的序号肯定是大于i的。

import java.util.*;

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> permutes = new ArrayList<List<Integer>>();
        
        if(num.length == 0)
        	return permutes;
        else if(num.length == 1)
        {
        	permutes.add(new ArrayList<Integer>());
        	permutes.get(0).add(num[0]);
        	return permutes;
        }
        
        List<List<Integer>> prepermutes = permuteUnique(Arrays.copyOfRange(num, 1,num.length));
        
        for(int i=0;i<num.length;i++)
        {
        	for(List<Integer> pp : prepermutes)
        	{
        		List<Integer> p = new ArrayList<Integer>();
        		boolean flag = false;
        		
        		for(int j=0;j<i;j++)
        		{
        			if(pp.get(j) == num[0])
        			{
        				flag = true;
        				break;
        			}
        			p.add(pp.get(j));
        		}
        		
        		if(flag == true)
        			continue;
        		
        		p.add(num[0]);
        		for(int j=i;j<num.length-1;j++)
        			p.add(pp.get(j));
        		
        		permutes.add(p);
        	}
        }
        
      return permutes;
    }
}