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

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:

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:

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);
        }
    }
}