The Unique Permutations Algorithm with Duplicate Elements

  • Time：2020-09-17 14:26:24
  • Class：Weblog
  • Read：28

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:

1
2
3
4
5

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

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) —

Recommend：
Things To Keep in Mind When Starting a Wedding Blog
Best Topics and Themes for Driving Traffic to Your Blog
Want to Start a Blog For Your Family Tree? Here’s How Anyone Can
Tips for Local Business Blogs
5 Tips to Drive Traffic to Your Blog
Ideas to Help You Set Up the Home Office of Your Dreams
Wix vs Squarespace 2020 – Things You Must Know
How to Delete N Nodes After M Nodes of a Linked List?
Bruteforce Algorithm to Find the Unique Positive Integer Whose S
Clone (Deep Copy) Binary Tree With Random Pointer using Hash Map
Share：Facebook Twitter
Comment list
Comment add