Solution Explanation: Permutations II

This problem asks to generate all unique permutations of a given array containing potentially duplicate numbers. The solution uses a backtracking approach enhanced with sorting and duplicate handling.

Approach:

1. Sorting: The input array nums is first sorted. This crucial step groups identical numbers together, simplifying duplicate detection during permutation generation.

2. Backtracking (DFS): A depth-first search (DFS) function, dfs(i), recursively explores all possible permutations. i represents the index of the element currently being placed in the permutation.

   • Base Case: If i equals the length of nums, a complete permutation (t) has been formed. This permutation is added to the result list ans.

   • Recursive Step: The function iterates through nums. For each element nums[j], it checks two conditions:

     • vis[j]: This boolean array tracks whether the element at index j has already been used in the current permutation. It prevents revisiting elements within a single permutation.
     • (j and nums[j] == nums[j - 1] and not vis[j - 1]): This condition prevents duplicates. If the current element is identical to the previous one and the previous one hasn't been used yet, it skips the current element to avoid generating redundant permutations.

   • If both conditions are false (the element is available), it's added to the current permutation t, marked as used (vis[j] = true), and the dfs function recursively calls itself to fill the next position (dfs(i + 1)). After the recursive call, vis[j] is set back to false to allow the element to be used in other permutations.

Time Complexity: O(n * n!)

• The array is sorted in O(n log n), but this is dominated by the backtracking part.
• The backtracking explores all possible permutations, which is n!. For each permutation, it takes O(n) time to check the conditions and make the selections. Hence, the overall time complexity is O(n * n!).

Space Complexity: O(n)

• The space complexity is dominated by the recursive call stack in the worst case, which can reach a depth of n. The vis array and t array both take O(n) space.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#):

The provided code snippets demonstrate the algorithm in several programming languages. They all follow the same logic: sorting, backtracking with duplicate handling, and the use of a boolean array to track visited elements. Note that minor syntactic differences exist between languages, but the core algorithm remains the same.

Example Usage (Python):

solution = Solution()
nums = [1, 1, 2]
result = solution.permuteUnique(nums)
print(result)  # Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

This detailed explanation clarifies the algorithm, complexities, and code implementation of the solution for generating unique permutations with duplicates. The use of sorting and careful duplicate checking ensures efficient and correct generation of all unique permutations.