Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
How to Get Unique Permuations in C++?
In fact, the C++ STL algorithm header provides the std::next_permutation() which deals with the duplicate elements in the candidate array. We just need to sort the array, then start permutating until the next_permutation() returns false.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> r; sort(begin(nums), end(nums)); r.push_back(nums); while (next_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } }; |
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> r;
sort(begin(nums), end(nums));
r.push_back(nums);
while (next_permutation(begin(nums), end(nums))) {
r.push_back(nums);
}
return r;
}
};Recursive Permutation Algorithm without Duplicate Result
Similar to The Permutation Algorithm for Arrays using Recursion, we can do this recursively by swapping two elements at each position. However, we need to keep tracking of the solution that has also been in the permutation result using a hash set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> r; dfs(nums, 0, r, ""); return r; } private: unordered_set<string> used; void dfs(vector<int>& nums, int index, vector<vector<int>> &r, string key) { if (index == nums.size()) { if (!used.count(key)) { r.push_back(nums); used.insert(key); } } else { for (int i = index; i < nums.size(); ++ i) { swap(nums[i], nums[index]); dfs(nums, index + 1, r, key + std::to_string(nums[index])); swap(nums[i], nums[index]); } } } }; |
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> r;
dfs(nums, 0, r, "");
return r;
}
private:
unordered_set<string> used;
void dfs(vector<int>& nums, int index, vector<vector<int>> &r, string key) {
if (index == nums.size()) {
if (!used.count(key)) {
r.push_back(nums);
used.insert(key);
}
} else {
for (int i = index; i < nums.size(); ++ i) {
swap(nums[i], nums[index]);
dfs(nums, index + 1, r, key + std::to_string(nums[index]));
swap(nums[i], nums[index]);
}
}
}
};In the worst cases, both implementations are O(N!) as N! is the total number of permutation results for N-size elements.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Python Coding Reference: index() and find() for string (substring), tuple and list
Next Post: How to Design a Design Bounded Blocking Queue in Python using Threading Library?