Tricky Pemutations

#1

question link is :- https://hack.codingblocks.com/contests/c/537/737
Please tell me where i am wrong in my code
My code is:-

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

void permutations(char *in,int i){
if(in[i]==’\0’){
cout<<in<<endl;
return;
}

for(int j=i; in[j]!='\0'&&((i==j)||(in[i]!=in[j])) ;j++){
    swap(in[i],in[j]);
    
    permutations(in,i+1);
    
    //backtracking
    swap(in[i],in[j]);
    
}

}

int main() {
char in[100];
cin>>in;

//sort(in,in+strlen(in));

permutations(in,0);

return 0;

}

#2

it is mentioned in question .
you should not print duplicates.
So use (vector < set > s) to store all permutation and it will discard all duplicates and return you all the permutation in lexo order.

Hope u get it . Hit like if u get it.
TIP : If u know STL then use string class and vectors rather than char array or normal array

Ohh sorry…i didnot see that u cant use set as mentioned in question

#3

FOR INPUT : BAA
Correct ouput
AAB
ABA
BAA
Your output
BAA
ABA
AAB
AAB
ABA.

store them in vector and sort them and while iterating vector check
if previous string not equal to current string then it would be answer otherwise discard it.

#4

i think the string is immutable then how can we swap the elements present in it

#5

btw can u tell me what is the error in this code of mine , it is showing WA for some Testcases
#include<bits/stdc++.h>
using namespace std;

vector v;

void permutations(char *in,int i){
if(in[i]==’\0’){
v.push_back(in);
//cout<<in<<endl;
return;
}

for(int j=i; in[j]!='\0'&&((i==j)||(in[i]!=in[j])) ;j++){
    swap(in[i],in[j]);
    
    permutations(in,i+1);
    
    //backtracking
    swap(in[i],in[j]);
    
}

}

int main() {
char in[100];
cin>>in;

//sort(in,in+strlen(in));

permutations(in,0);

sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
    cout<<v[i]<<endl;
}

return 0;

}

#6

I have done it no need to read previous comment.

#7

Hey Sanyam, that’s great you have done it. One more thing is strings in c++ are not immutable and for knowing how are they you can refer this.

1 Like
#8

ok thanks…