Permutations with duplicates

1. Non-recursive solution

public List permuteUnique(int[] nums) { List res=new ArrayList(); if(nums.length==0) return res; res.add(new ArrayList<Integer>()); for(int n:nums){ List next=new ArrayList(); for(List<Integer> list:res){ for(int i=0;i<=list.size();i++){ List<Integer> nextList=new ArrayList<Integer>(list); if(i==list.size()) {nextList.add(n); next.add(nextList); break;} nextList.add(i,n); next.add(nextList); if(list.get(i)==n) break; // this line deal with the duplicates } } res=next; } return res; }

1. Recursive solution

public class Solution { public List permuteUnique(int[] nums) { List res = new ArrayList(); Arrays.sort(nums); LinkedList<Integer> list = new LinkedList<Integer>(); for (int num : nums) list.add(num); permute(list, 0, res); return res; } private void permute(LinkedList<Integer> nums, int start, List res){ if (start == nums.size() - 1){ res.add(new LinkedList<Integer>(nums)); return; } for (int i = start; i < nums.size(); i++){ if (i > start && nums.get(i) == nums.get(i - 1)) // this line deal with the duplicates continue; nums.add(start, nums.get(i)); // put ith element in the fornt nums.remove(i + 1); // remove the moved element, now it is in (i+1)th position permute(nums, start + 1, res); // permute the rest nums.add(i + 1, nums.get(start)); // put the moved element back nums.remove(start); // delete the residual } } }