2014年4月14日 星期一

[LeetCode] Permutations II

Problem:
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].
Solution:O(n!)
public class Solution {
    public ArrayList> permuteUnique(int[] num) {
        ArrayList> list = new ArrayList>();
        if(num == null || num.length == 0)
            return list;
        if(num.length == 1){
            ArrayList r = new ArrayList();
            r.add(num[0]);
            list.add(r);
            return list;
        }
        ArrayList> slist = permuteUnique(Arrays.copyOfRange(num,1,num.length));
        HashSet> set = new HashSet>(); 
        for(ArrayList l:slist){
            for(int i=0; i<=l.size();i++){
                l.add(i,num[0]);
                ArrayList t = new  ArrayList(l);
                if(!set.contains(t)){
                    set.add(t);
                    list.add(t);
                }
                l.remove(i);
            }
        }
        return list;
    }
}

沒有留言:

張貼留言