Problem Explanation
We are given an array A, We have to give all unique permutattions of the elements of A.
Approach
We use Recursion and Backtracking to get every permutation from the array. To avoid duplicates being treated as different elements, we store the elements in a map with their frequency. When the function is called, if the map is empty then all the elements have been used, so we push the permutation in our vector of permutations. Otherwise, we iterate in the map and use that elements in the permutations and call the function again with the updated map.
Code
#include <bits/stdc++.h>
using namespace std;
void uniquePermutations(map<int,int>& elementsFreq, vector<int>& currentPermutation, vector<vector<int>>& allPermutations) {
if (elementsFreq.empty()) {
allPermutations.push_back(currentPermutation);
return;
}
for (auto element: elementsFreq) {
int num = element.first, freq = element.second;
currentPermutation.push_back(num);
map<int, int> newElementsFreq = elementsFreq;
if (freq == 1)
newElementsFreq.erase(num);
else
newElementsFreq[num]--;
uniquePermutations(newElementsFreq, currentPermutation, allPermutations);
currentPermutation.pop_back();
}
}
int main() {
int t;
cin>>t;
while(t--){
int N;
cin>>N;
map<int,int> elementsFreq;
for (int i=0; i<N; i++) {
int x;
cin>>x;
elementsFreq[x]++;
}
vector<vector<int>> allPermutations;
vector<int> currentPermutation;
uniquePermutations(elementsFreq, currentPermutation, allPermutations);
cout<<allPermutations.size()<<endl;
for (auto& permutation: allPermutations) {
for (int i: permutation)
cout<<i<<" ";
cout<<endl;
}
}
return 0;
}