You are given an array of integers that may contain duplicate elements. Your task is to generate all unique permutations of the array. Permutations that are identical should not be repeated in the result.
Example 1
Input: arr[] = [1]
Output: [1]
Explanation: Only one arrangement is possible.
Example 2
Input: arr[] = [1 1 2]
Output: [1 1 2] [1 2 1] [2 1 1]
Explanation: Rearrangements are formed, but duplicate orders are removed.
Example 3
Input: arr[] = [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 different orderings are generated while avoiding repeated permutations caused by duplicates.
Sign in to write, run, and submit your solution against the full test suite.