本文共 1201 字，大约阅读时间需要 4 分钟。
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 > permuteUnique(int[] num) { List > opt = new ArrayList >(); // edge case if(num.length==0){return opt;} // base case List firstLst = new ArrayList (); firstLst.add(num[0]); opt.add(firstLst); // iteration for(int i =1;i < num.length;i++){ HashSet > visited = new HashSet >(); int numOfLastOpt = opt.size(); for(int j = 0;j < numOfLastOpt;j++){ // insert new int into each valid gap int positions = opt.get(j).size(); for(int u = 0;u <= positions;u++){ if(u != 0){ if(opt.get(j).get(u-1) != num[i]){ List newLst = new ArrayList (opt.get(j)); newLst.add(u,num[i]); if(!visited.contains(newLst)){ opt.add(newLst); visited.add(newLst); } } }else{ List newLst = new ArrayList (opt.get(j)); newLst.add(u,num[i]); if(!visited.contains(newLst)){ opt.add(newLst); visited.add(newLst); } } } } // delete previous opt for(int j = 0;j < numOfLastOpt;j++){ opt.remove(0); } } return opt; }}
转载地址：http://upuni.baihongyu.com/