 # Implementing next_permutation library in c++ using recursion

Hey , i was implementing next_permutation using recursion in c++. But i am getting wrong answer on 7/10 of test cases.

Heres the question-

Given a string containing duplicates, print all its distinct permutations such that there are no duplicate permutations and all permutations are printed in a lexicographic order.

NOTE: DO NOT USE MAP OR SET.

Input Format:

The first and only line of the test case contains the input string.

Constraints:

Length of the string <= 8

Output Format

Print all the distinct permutations in a lexicographic order such that each permutation is in a new line. Note that there should not be any duplicate permutations.

Sample Input

ABA

Sample Output

AAB ABA BAA

My solution -

`````` #include<bits/stdc++.h>
using namespace std;

//checking is current element matches with any element then it will produce redundant results
bool checkif(string &in,int i,int j){
for(int k=i;k<j;k++){
if(in[k] == in[j])
return 0;
}
return 1;
}

void distinctPermutations(string &in,int i){
//Base case

if(in[i]==NULL){
cout<<in<<endl;
return;
}

//Recursive case

bool flag=0;
for(int j=i;in[j]!=NULL;j++){

bool check = checkif(in,i,j);

if(check) {
swap(in[j],in[i]);
distinctPermutations(in,i+1);
swap(in[j],in[i]);
}

}
}

int main() {
string in;
cin>>in;
sort(in.begin(),in.end());
distinctPermutations(in,0);
return 0;
}``````

Here, We go!

``````#include<bits/stdc++.h>
using namespace std;
void ok(string s, int l){
if(l + 1 ==(int)s.size()){
cout << s << endl;
return;
}
for(int i=l;i<(int)s.size();i++){
if(i==l)ok(s,l+1);
else if(s[i]!=s[l]){
swap(s[i],s[l]);
sort(s.begin()+l+1,s.end());
ok(s,l+1);
swap(s[i],s[l]);
}
}
}
int main(){
string s;
cin >> s;
// before calling ok() make sure s is sorted
sort(s.begin(),s.end());
ok(s,0);
return 0;
}``````
2 Likes

Hey thanks for the solution. Can you please explain why you have used sort(s.begin()+l+1,s.end()) before ok(s,l+1) with an example @meet2mky