Leetcode: Permutations II

The question that I am trying to answer is as follows:

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. 

Example:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints: 

1 <= nums.length <= 8

-10 <= nums[i] <= 10

So how do we approach this problem?

We approach this problem with a solution called backtracking.

We need N stages to generate a permutation, as follows:

We can build a hash table with each unique number and its occurrence as its corresponding value.

We implement a backtracking function and invoke the function involving the hash table. 

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> results = new ArrayList<>();

        HashMap<Integer, Integer> counter = new HashMap<>();

        if(!counter.containsKey(num)){

            counter.put(num, 0);

        }

        counter.put(num, counter.get(num) + 1);

        LinkedList<Integer> comb = new LinkedList<>();

        this.backtrack(comb, nums.length, counter, results);

        return results;

    }

    protected void backtrack(LinkedList<Integer> comb, Integer N, HashMap<Integer, Integer> counter, List<List<Integer>> results){

        if(comb.size() == N){

            results.add(new ArrayList<Integer> (comb));

            return;

        }

        for(Map.Entry<Integer, Integer> entry : counter.entrySet()){

            Integer num = entry.getKey();

            Integer count = entry.getValue();

            if (count == 0) continue;

            comb.addLast(num);

            counter.put(num, count - 1);

            backtrack(comb, N, counter, results);

            comb.removeLast;

            counter.put(num, count);

        }

    }

}

Such is an implementation. The number of permutations will be at N!. It would take NxN! steps to generate the permutations, and the total space complexity is O(N) since we need O(N) space for each recursion.