Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
Example 2:
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] <= 10Problem Overview: You are given an integer array that may contain duplicates. The task is to return all unique permutations of the numbers. The challenge is avoiding duplicate permutations that naturally appear when identical values exist in the input array.
Approach 1: Backtracking with Used Array (O(n! * n) time, O(n) space)
This is the most common approach used in interviews. Start by sorting the array so duplicate numbers appear next to each other. During backtracking, maintain a used[] array that tracks which indices are already included in the current permutation path. When iterating through the array, skip a number if it is the same as the previous one and the previous copy was not used in the current branch. This rule prevents generating duplicate permutations. The recursion builds permutations step by step and adds them to the result once the path length reaches n. Time complexity is O(n! * n) because there are up to n! permutations and each permutation construction costs O(n). Space complexity is O(n) for the recursion stack and used array (excluding output).
Approach 2: Recursive Swap with Set (O(n! * n) time, O(n) space)
This approach generates permutations by swapping elements in place, similar to classic permutation generation. At each recursion level, iterate from the current index to the end and swap the chosen element into the current position. A local HashSet or set is used at each level to track which values have already been placed at that position. If a value has already been used in that level, skip it to prevent duplicate permutations. After exploring a branch, swap the elements back to restore the original array before continuing. This technique relies heavily on array manipulation and backtracking. The time complexity remains O(n! * n) because each permutation requires copying or recording the current array state, and the recursion depth is n. Space complexity is O(n) due to recursion depth and the per-level set.
Recommended for interviews: Backtracking with a used array and sorted input is the approach most interviewers expect. It clearly demonstrates how you handle duplicates while generating permutations. Starting with naive permutation generation shows baseline understanding, but adding the duplicate-skipping rule proves you understand pruning and efficient backtracking design. The swap-with-set approach is also valid but slightly less intuitive because duplicate control happens through an additional set at each recursion level.
This approach uses backtracking to generate permutations and a boolean array to track used elements in the current permutation combination. By sorting the array at the start, we can easily skip duplicates.
This Python solution uses recursion and backtracking to generate permutations. Sorting the nums list initially helps to efficiently skip duplicates by checking if the element is the same as the previous one and if the previous one has been used.
Python
Java
JavaScript
C#
C
Time Complexity: O(n * n!) due to the generation of all permutations.
Space Complexity: O(n!) for storing the permutations and O(n) for the recursion stack.
This method carries out permutations by recursively swapping elements and employs a set to track unique permutations and avoid generating duplicate results. It does not require sorting initially but uses swaps directly to generate permutations.
Implementing permutations through swapping allows the program to manage the sequence in-place and recursively form permutations, collecting results in a set for uniqueness.
Python
Java
JavaScript
C#
Time Complexity: O(n * n!)
Space Complexity: O(n * n!) because of the set used to store permutations.
We can first sort the array so that duplicate numbers are placed together, making it easier to remove duplicates.
Then, we design a function dfs(i), which represents the current number to be placed at the i-th position. The specific implementation of the function is as follows:
i = n, it means we have filled all positions, add the current permutation to the answer array, and then return.nums[j] for the i-th position, where the range of j is [0, n - 1]. We need to ensure that nums[j] has not been used and is different from the previously enumerated number to ensure that the current permutation is not duplicated. If the conditions are met, we can place nums[j] and continue to recursively fill the next position by calling dfs(i + 1). After the recursive call ends, we need to mark nums[j] as unused to facilitate subsequent enumeration.In the main function, we first sort the array, then call dfs(0) to start filling from the 0th position, and finally return the answer array.
The time complexity is O(n times n!), and the space complexity is O(n). Here, n is the length of the array. We need to perform n! enumerations, and each enumeration requires O(n) time to check for duplicates. Additionally, we need a marker array to mark whether each position has been used, so the space complexity is O(n).
Similar problems:
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Backtracking with Used Array | Time Complexity: O(n * n!) due to the generation of all permutations. |
| Recursive Swap with Set | Time Complexity: O(n * n!) |
| Sorting + Backtracking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Used Array | O(n! * n) | O(n) | Most common interview solution; easy duplicate pruning after sorting |
| Recursive Swap with Set | O(n! * n) | O(n) | Useful when generating permutations in-place without a separate used array |
Permutations II - Backtracking - Leetcode 47 • NeetCode • 121,369 views views
Watch 9 more video solutions →Practice Permutations II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor