Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
In my previous post, we have discussed three solutions where the numbers are unique. Recommend to read that post before proceeding to this.
This problem can also be solved in 4 different ways. Namely:
- Backtracking
- Using set
- STL
- Hashmap
We shall discuss first 3 solutions here:
1. Backtracking
To understand backtracking I recommend reading this topic, I 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 the same. If both are the same, then we skip the current iteration and go to the next iteration.
2. Using sets or Modified Permutation 1
Please check Permutation 1 problem before going through this solution.
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++
#include<iostream> #include <vector> #include<unordered_set> using namespace std; void permutation_recursive_backtrack(vector<int> &input_set, vector<int> ¤t_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 )
Please comment below with your solution and your doubts if any.