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

Solution:

We count the number of elements an element appears in a hashmap (we used a LinkedHashMap to guarantee that the order of iteration is always the same). Then we use a recursive solution where we iterate through the different elements of the collection and keeping the number of times an element has been used in an array.

import java.util.LinkedHashMap;

public class Solution {

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) 

    {

        LinkedHashMap<Integer, Integer> numberofElements = new LinkedHashMap<Integer, Integer>();

        for(int i=0; i<num.length; i++)

        {

            if(!numberofElements.containsKey(num[i]))

                numberofElements.put(num[i],1);

            else

                numberofElements.put(num[i],numberofElements.get(num[i])+1);

        }

        ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> permutation = new ArrayList<Integer>();

        permuteUnique(num, sol, permutation, numberofElements, new int[numberofElements.size()]);

        return sol;

    }

    

    public void permuteUnique(int[] num, ArrayList<ArrayList<Integer>> sol, ArrayList<Integer> permutation, LinkedHashMap<Integer, Integer>numberofElements, int[] used) 

    {

        if(permutation.size()==num.length)

        {

            sol.add((ArrayList<Integer>)permutation.clone());

            return;

        }

        int i=0;

        for(Integer val: numberofElements.keySet())

        {

            if(used[i]<numberofElements.get(val))

            {

                used[i]++;

                permutation.add(val);

                permuteUnique(num, sol, permutation, numberofElements, used);

                permutation.remove(permutation.size()-1);

                used[i]--;

            }

            i++;

        }

    }

}