Problem Statement

Given a list of numbers nums that might have duplicates, return all unique arrangements of the numbers in any order.

Examples

Example 1:

• Input: nums = [1, 2, 2]
• Output: [[1,2,2],[2,1,2],[2,2,1]]
• Explanation: There are a total of 6 permutations of [1, 2, 2] list but only 3 are unique.

Example 2:

• Input: nums = [2, 2, 3]
• Output: [[2,2,3],[2,3,2],[3,2,2]]
• Explanation: All unique permutations of the list [2, 2, 3] are shown above.

Example 3:

• Input: nums = [1, 2, 2, 3]
• Output: [[1,2,2,3],[1,2,3,2],[1,3,2,2],[2,1,2,3],[2,1,3,2],[2,2,1,3],[2,2,3,1],[2,3,1,2],[2,3,2,1],[3,1,2,2],[3,2,1,2],[3,2,2,1]]
• Explanation: All unique permutations of the list [1, 2, 2, 3] are shown above.

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

Solution

To solve this problem, we need to generate all possible permutations of the input list while ensuring that we do not include duplicate permutations. We can achieve this by sorting the list first, which helps in skipping duplicate numbers during the permutation process. Using a backtracking approach, we build permutations incrementally by adding one number at a time and ensuring that each number is not used more than once at a specific position. By marking numbers that have been used in the current recursive call, we can avoid duplicates effectively.

This approach works well because it systematically explores all potential permutations while skipping over duplicate entries. By leveraging a sorted list and a used array, we ensure each permutation is unique and all possible permutations are considered.

Step-by-Step Algorithm

1. Sort the input array nums to handle duplicates easily.
2. Initialize an empty list result to store all unique permutations.
3. Define a helper function backtrack that takes the current permutation tempList, a boolean array used to track used elements, and nums.
4. Check if the length of tempList is equal to the length of nums:
   • If true, add a copy of tempList to result.
   • If false, proceed to the next step.
5. Iterate over each element in nums:
   • Skip elements that are already used or duplicate elements that are not used in the current recursive call.
   • Mark the current element as used.
   • Add the current element to tempList.
   • Recursively call backtrack with the updated tempList and used array.
   • Backtrack by unmarking the current element and removing it from tempList.
6. Call the backtrack function with an empty tempList and a used array of False values.
7. Return the result list containing all unique permutations.

Algorithm Walkthrough

Using the input nums = [1, 2, 2]:

1. Sort the array: The sorted array remains [1, 2, 2].
2. Initialize result: result = [].
3. Call backtrack with tempList = [] and used = [False, False, False].

First Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, not used. Add to tempList and mark as used.
     • tempList = [1], used = [True, False, False].
     • Call backtrack with updated tempList and used.

Second Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, already used. Skip.
   • i = 1:
     • nums[1] = 2, not used. Add to tempList and mark as used.
     • tempList = [1, 2], used = [True, True, False].
     • Call backtrack with updated tempList and used.

Third Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, already used. Skip.
   • i = 1:
     • nums[1] = 2, already used. Skip.
   • i = 2:
     • nums[2] = 2, not used. Add to tempList and mark as used.
     • tempList = [1, 2, 2], used = [True, True, True].
     • Call backtrack with updated tempList and used.

Fourth Level:

1. tempList length equals nums length.
   • Add [1, 2, 2] to result.
   • result = [[1, 2, 2]].

Backtrack:

1. Unmark nums[2] and remove from tempList.
   • tempList = [1, 2], used = [True, True, False].
2. Return to the previous level.

Backtrack:

1. Unmark nums[1] and remove from tempList.
   • tempList = [1, 2], used = [True, False, True].
2. Return to the previous level.

Third Level:

1. Continue iteration:
   • i = 2:
     • Already processed. Skip.

Backtrack:

1. Unmark nums[2] and remove from tempList.
   • tempList = [1], used = [True, False, False].
2. Return to the previous level.

First Level:

1. Continue iteration:
   • i = 1:
     • nums[1] = 2, not used. Add to tempList and mark as used.
     • tempList = [2], used = [False, True, False].
     • Call backtrack with updated tempList and used.

Second Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, not used. Add to tempList and mark as used.
     • tempList = [2, 1], used = [True, True, False].
     • Call backtrack with updated tempList and used.

Third Level:

1. Iterate over nums:
   • i = 0:
     • Already used. Skip.
   • i = 1:
     • Already used. Skip.
   • i = 2:
     • nums[2] = 2, not used. Add to tempList and mark as used.
     • tempList = [2, 1, 2], used = [True, True, True].
     • Call backtrack with updated tempList and used.

Fourth Level:

1. tempList length equals nums length.
   • Add [2, 1, 2] to result.
   • result = [[1, 2, 2], [2, 1, 2]].

Backtrack:

1. Unmark nums[2] and remove from tempList.
   • tempList = [2, 1], used = [True, True, False].
2. Return to the previous level.

Third Level:

1. Continue iteration:
   • i = 2:
     • Already processed. Skip.

Backtrack:

1. Unmark nums[0] and remove from tempList.
   • tempList = [2], used = [False, True, False].
2. Return to the previous level.

Second Level:

1. Continue iteration:
   • i = 1:
     • Already processed. Skip.
   • i = 2:
     • nums[2] = 2, not used. Add to tempList and mark as used.
     • tempList = [2, 2], used = [False, True, True].
     • Call backtrack with updated tempList and used.

Third Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, not used. Add to tempList and mark as used.
     • tempList = [2, 2, 1], used = [True, True, True].
     • Call backtrack with updated tempList and used.

Fourth Level:

1. tempList length equals nums length.
   • Add [2, 2, 1] to result.
   • result = [[1, 2, 2], [2, 1, 2], [2, 2, 1]].

Return Result:

• All permutations of the [1, 2, 2] list are [[1, 2, 2], [2, 1, 2], [2, 2, 1]].

Code