For a given integer list, nums, which might contain duplicates, return all possible unique permutations derived from nums.

Note: The order in which the permutations appear doesn’t matter.

Constraints:

• $1 \leq$ nums.length $\leq 8$

• $-10 \leq$ nums[i] $\leq 10$

To solve this problem, we use the backtracking approach combined with a frequency counter to avoid redundant permutation calculations. This approach ensures that we only generate unique permutations by keeping track of the number of occurrences of each element in the array. This method is related to the subsets pattern, where the goal is to explore all possible subsets of a given set of elements. In the context of permutations, instead of subsets, we explore all possible unique arrangements of the elements. Just as the subsets pattern involves making decisions at each step (whether to include an element in the subset), the backtracking approach for permutations involves deciding which element to add next while ensuring that duplicates are handled correctly.

The steps of the algorithm are as follows:

1. We initialize an empty list, results, which will store all the unique permutations of the given array.

2. We use a hash map to count the occurrences of each element in the array. This helps efficiently manage duplicate elements and ensures that each permutation is unique.

3. The backtracking function is a recursive function that builds permutations by selecting one element at a time. It takes two parameters: combination, which is the current permutation being built, and numbers, which is the hash map that tracks the remaining elements available for permutation.

   1. Base case: The base case of the recursion occurs when the length of combination equals the length of nums. At this point, the current permutation is complete, and we append a copy of combination to the results list.

   2. Recursive case: We iterate over the elements in numbers. For each element, if it still has occurrences left (numbers[candidate] > 0), we:

      1. Append the element to the current combination.

      2. Decrease the count of the element in the hash map.

      3. Recursively call backtracking to continue building the permutation.

      4. After returning from the recursion, we backtrack by removing the last element added to combination and restoring the count of that element in the hash map.

4. After all permutations have been generated, the results list, which contains all unique permutations, is returned.

Let’s look at the illustration below to better understand the solution.