Implementing next_permutation library in c++ using recursion

help
, ,
1

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() {
// your code goes here
string in;
cin>>in;
sort(in.begin(),in.end());
distinctPermutations(in,0);
return 0;
}
2

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
3

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