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]`

.

**Understand the problem:**

The problem is an extension to Permutation I, the mainly difference is it exists the duplicated elements, and we return only unique permutations.

**Solution:**

The solution is very similar to the permutation I, the only difference is before we swap the number start and i, we check if between start and i has duplicates. If yes, it indicates that we visited the number before, so simply jump to next iteration.

**Code (Java):**

public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); permuteUnique(num, 0, result); return result; } private void permuteUnique(int[] num, int start, ArrayList<ArrayList<Integer>> result) { if (start >= num.length) { ArrayList<Integer> temp = toArrayList(num); result.add(temp); return; } for (int i = start; i < num.length; i++) { if (!containsDup(num, start, i)) { swap(num, i, start); permuteUnique(num, start + 1, result); swap(num, i, start); } } } private void swap(int[] num, int i, int j) { int temp = num[i]; num[i] = num[j]; num[j] = temp; } private ArrayList<Integer> toArrayList(int[] num) { ArrayList<Integer> temp = new ArrayList<Integer>(num.length); for (int i = 0; i < num.length; i++) { temp.add(num[i]); } return temp; } private boolean containsDup(int[] num, int start, int end) { for (int i = start; i <= end - 1; i++) { if (num[i] == num[end]) return true; } return false; } }

**Discussion:**

Note the method on how to determine the duplicates. This the most tricky part of this problem.

**Update on 10/27/14:**

## No comments:

## Post a Comment