Given a collection of numbers that might contain duplicates, return all possible unique permutations in C++

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

In my pervious post we have discussed three solutions where the numbers are unique. Recommend to read that post before proceeding to this.

Given a collection of distinct integers, return all possible permutations.

This problem can also be solved in 4 different ways. Namely:

1. Backtracking
2. Using set
3. STL
4. Hashmap

We shall discuss first 3 solutions here:

1. Backtracking

To understand backtracking I recommend this topic

Given an array of non repeating numbers and a key, find all the unique combinations in that array, where the sum of those combination is equal to the key.

where have explained in detail, what backtracking is.

Coming to the solution here, we shall take a Boolean array, we update that array, if we have used the element we set that index to true.

Then we check if the previous element and present element are same. If both are same, then we skip the current iteration and go to next iteration.

2. Using sets or Modified Permutation 1

Please check Permutation 1 problem before going through this solution.

Given a collection of distinct integers, return all possible permutations.

The only difference between the Permutation 1 and this solution is that we use a set to keep track if we have used the element or not.

Then we check the count of the set at that index, if the count is greater than 0, we skip the current iteration and go with next iteration.

3. Using Next permutation

Using STl, first we need to sort the input array. Else it will start from the larger number and the output will be wrong.

Implementation in C++

/*
* File     : Permutation II
* Author   : ajay.thousand@gmail.com
* Purpose  : To find permutation when duplicate numbers are present
* Copyright: @ prodevelopertutorial.com
*/
#include<iostream>
#include <vector>
#include<unordered_set>

using namespace std;


void permutation_recursive_backtrack(vector<int> &input_set, vector<int> &current_set, vector<vector<int> > &final_result_set, int begin, bool number_used[])   
{
    //base condition for recursive function 
    if (current_set.size() >= input_set.size()) 
    {
        // add the number pair to the final result set.
        final_result_set.push_back(current_set);
        return;
    }

    for (int i = begin; i < input_set.size(); i++) 
    {
        if (!number_used[i])
        {

            if (i > 0 && input_set[i] == input_set[i -1] && number_used[i -1])
            {
                continue;
            }
            number_used[i] = true;
            current_set.push_back(input_set[i]);
            permutation_recursive_backtrack(input_set, current_set, final_result_set, 0, number_used);   
            current_set.pop_back();

            //reset the boolean array
            number_used[i] = false;
        }

    }
}

vector<vector<int> > get_permutation_using_backtracking(vector<int> &input_set) 
{
    vector<vector<int> > final_result_set;
    vector<int> current_set;

    bool number_used [input_set.size()];
    
    permutation_recursive_backtrack(input_set, current_set, final_result_set, 0, number_used);
    return final_result_set;
}



void permutation_recursive_set(vector<int> &input_set, int begin, vector<vector<int> > &final_result_set)   
{
    //base condition for recursive function 
    if (begin >= input_set.size()) 
    {
        // add the number pair to the final result set.
        final_result_set.push_back(input_set);
        return;
    }

    // to detect the duplicate elements
    unordered_set<int> set;
    // i will be the index of each fixed digit
        for (int i = begin; i < input_set.size(); i++) 
        {
            // check if the count at that index is greater than 0
            if (set.count(input_set[i]) > 0)
                continue;

            //if it is not '0', then insert that element at that index.
            set.insert(input_set[i]);
            
            swap(input_set[begin], input_set[i]);

            permutation_recursive_set(input_set, begin + 1, final_result_set);
            // reset the swapped numbers
            swap(input_set[begin], input_set[i]);

        }
}

vector<vector<int> > get_permutation_using_set(vector<int> &input_set) 
 {
    vector<vector<int> > final_result_set;
        
    permutation_recursive_set(input_set, 0, final_result_set);
    return final_result_set;
}

    
vector<vector<int> > using_next_permutation(vector<int>& input_set)
{

    sort(input_set.begin(), input_set.end());

    vector<vector<int> > final_result_set;

    sort(input_set.begin(),input_set.end());
        
    do {
        final_result_set.push_back(input_set);
    } while (next_permutation(input_set.begin(), input_set.end()));

    return final_result_set;
}



int main()
{
    vector<int> input_set;
    input_set.push_back(1);
    input_set.push_back(1);
    input_set.push_back(2);
    
    //vector<vector<int> > final_set =  get_permutation_using_backtracking(input_set);
    //vector<vector<int> > final_set =  get_permutation_using_set(input_set);
    vector<vector<int> > final_set =  using_next_permutation(input_set);

    // print the output
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << " ( ";
            for (int j = 0; j < final_set[i].size(); j++)
                cout << final_set[i][j] << " ";
            cout << ")";
        }
        cout<<endl;
    }

	return 0;
}

Output:

( 1 1 2 )
( 1 2 1 )
( 2 1 1 )