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; } }
沒有留言:
張貼留言