0% completed
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
- Sort the input array
nums
to handle duplicates easily. - Initialize an empty list
result
to store all unique permutations. - Define a helper function
backtrack
that takes the current permutationtempList
, a boolean arrayused
to track used elements, andnums
. - Check if the length of
tempList
is equal to the length ofnums
:- If true, add a copy of
tempList
toresult
. - If false, proceed to the next step.
- If true, add a copy of
- 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 updatedtempList
andused
array. - Backtrack by unmarking the current element and removing it from
tempList
.
- Call the
backtrack
function with an emptytempList
and aused
array ofFalse
values. - Return the
result
list containing all unique permutations.
Algorithm Walkthrough
Using the input nums = [1, 2, 2]
:
- Sort the array: The sorted array remains
[1, 2, 2]
. - Initialize
result
:result = []
. - Call
backtrack
withtempList = []
andused = [False, False, False]
.
First Level:
- Iterate over
nums
:- i = 0:
nums[0] = 1
, not used. Add totempList
and mark as used.tempList = [1]
,used = [True, False, False]
.- Call
backtrack
with updatedtempList
andused
.
- i = 0:
Second Level:
- Iterate over
nums
:- i = 0:
nums[0] = 1
, already used. Skip.
- i = 1:
nums[1] = 2
, not used. Add totempList
and mark as used.tempList = [1, 2]
,used = [True, True, False]
.- Call
backtrack
with updatedtempList
andused
.
- i = 0:
Third Level:
- 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 totempList
and mark as used.tempList = [1, 2, 2]
,used = [True, True, True]
.- Call
backtrack
with updatedtempList
andused
.
- i = 0:
Fourth Level:
tempList
length equalsnums
length.- Add
[1, 2, 2]
toresult
. result = [[1, 2, 2]]
.
- Add
Backtrack:
- Unmark
nums[2]
and remove fromtempList
.tempList = [1, 2]
,used = [True, True, False]
.
- Return to the previous level.
Backtrack:
- Unmark
nums[1]
and remove fromtempList
.tempList = [1, 2]
,used = [True, False, True]
.
- Return to the previous level.
Third Level:
- Continue iteration:
- i = 2:
- Already processed. Skip.
- i = 2:
Backtrack:
- Unmark
nums[2]
and remove fromtempList
.tempList = [1]
,used = [True, False, False]
.
- Return to the previous level.
First Level:
- Continue iteration:
- i = 1:
nums[1] = 2
, not used. Add totempList
and mark as used.tempList = [2]
,used = [False, True, False]
.- Call
backtrack
with updatedtempList
andused
.
- i = 1:
Second Level:
- Iterate over
nums
:- i = 0:
nums[0] = 1
, not used. Add totempList
and mark as used.tempList = [2, 1]
,used = [True, True, False]
.- Call
backtrack
with updatedtempList
andused
.
- i = 0:
Third Level:
- Iterate over
nums
:- i = 0:
- Already used. Skip.
- i = 1:
- Already used. Skip.
- i = 2:
nums[2] = 2
, not used. Add totempList
and mark as used.tempList = [2, 1, 2]
,used = [True, True, True]
.- Call
backtrack
with updatedtempList
andused
.
- i = 0:
Fourth Level:
tempList
length equalsnums
length.- Add
[2, 1, 2]
toresult
. result = [[1, 2, 2], [2, 1, 2]]
.
- Add
Backtrack:
- Unmark
nums[2]
and remove fromtempList
.tempList = [2, 1]
,used = [True, True, False]
.
- Return to the previous level.
Third Level:
- Continue iteration:
- i = 2:
- Already processed. Skip.
- i = 2:
Backtrack:
- Unmark
nums[0]
and remove fromtempList
.tempList = [2]
,used = [False, True, False]
.
- Return to the previous level.
Second Level:
- Continue iteration:
- i = 1:
- Already processed. Skip.
- i = 2:
nums[2] = 2
, not used. Add totempList
and mark as used.tempList = [2, 2]
,used = [False, True, True]
.- Call
backtrack
with updatedtempList
andused
.
- i = 1:
Third Level:
- Iterate over
nums
:- i = 0:
nums[0] = 1
, not used. Add totempList
and mark as used.tempList = [2, 2, 1]
,used = [True, True, True]
.- Call
backtrack
with updatedtempList
andused
.
- i = 0:
Fourth Level:
tempList
length equalsnums
length.- Add
[2, 2, 1]
toresult
. result = [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
.
- Add
Return Result:
- All permutations of the
[1, 2, 2]
list are[[1, 2, 2], [2, 1, 2], [2, 2, 1]]
.
Code
Complexity Analysis
Time Complexity
The time complexity of generating all permutations is O(n! * n), where n is the length of the input array. This is because:
- There are n! permutations in total.
- For each permutation, it takes O(n) time to build and store it.
Additionally, sorting the array initially takes O(n log n) time. However, this sorting step is dominated by the permutation generation, making the overall time complexity O(n! * n).
Space Complexity
The space complexity is O(n * n!) because:
- We store all n! permutations, each of length n.
- The recursion stack can go as deep as n, and we maintain a temporary list of length n and a used array of length n.
Hence, the overall space complexity is O(n * n!).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible