[LeetCode] 47. Permutations II
[LeetCode] 47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]
have the following unique permutations:[ [1,1,2], [1,2,1], [2,1,1] ]
Thought process:
If the collection contains duplicate, I cannot only use the original method I used in "46. Permutations", because it will produce duplicate permutations. For example, if the collection is [0, 1, 1], the result will contain two [0, 1, 1]s.
The idea is to maintain a rule about which one of the duplicate numbers can appear in the permutations. To do this, I can sort the array and make sure that only the number with a smaller index can appear in a duplicate permutation.
For example, as I add numbers to the permutation list, if I found that I'm adding the second 1 while the first 1 is not in the list, that means the first 1 has already been used to make the exact same permutation. So I continue to the next iteration.
Read full article from [LeetCode] 47. Permutations II
No comments:
Post a Comment