Leetcode: Permutation 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].

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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

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 07/29/18:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

class Solution {     public List<List<Integer>> permuteUnique(int[] nums) {         List<List<Integer>> ans = new ArrayList<>();                   if (nums == null || nums.length == 0) {             return ans;         }                   Arrays.sort(nums);                   permuteHelper(0, nums, ans);                   return ans;     }           private void permuteHelper(int start, int[] nums, List<List<Integer>> ans) {         if (start >= nums.length) {             ans.add(new ArrayList<>(Arrays.stream(nums).boxed().collect(Collectors.toList())));             return;         }                   Set<Integer> set = new HashSet<>();         for (int i = start; i < nums.length; i++) {             if (set.add(nums[i])) {                 swap(nums, i, start);                 permuteHelper(start + 1, nums, ans);                 swap(nums, i, start);             }         }     }           private void swap(int[] nums, int i, int j) {         int temp = nums[i];         nums[i] = nums[j];         nums[j] = temp;     } }

Update 5/7/19:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

public class Solution {     /*      * @param :  A list of integers      * @return: A list of unique permutations      */     public List<List<Integer>> permuteUnique(int[] nums) {         // write your code here         List<List<Integer>> ans = new ArrayList<>();         if (nums == null || nums.length == 0) {             ans.add(new ArrayList<Integer>());             return ans;         }           Arrays.sort(nums);           boolean[] visited = new boolean[nums.length];         permuteUniqueHelper(nums, visited, new ArrayList<Integer>(), ans);         return ans;     }       private void permuteUniqueHelper(int[] nums, boolean[] visited, List<Integer> curList, List<List<Integer>> ans) {         if (curList.size() == nums.length) {             ans.add(new ArrayList<>(curList));             return;         }           for (int i = 0; i < nums.length; i++) {             if (visited[i]) {                 continue;             }             if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {                 continue;             }               visited[i] = true;             curList.add(nums[i]);             permuteUniqueHelper(nums, visited, curList, ans);             visited[i] = false;             curList.remove(curList.size() - 1);         }     } }