Problem is to create list of all possible combinations of letters of a given string. If two strings are with the same set of characters, the lexicographically smallest arrangement of the two strings should appear first.
For string "abcd" possible combinations would be:
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d
The code below is the cpp implementation for the problem above.
void print_comb_utils(string str, string tmp, int pos){
for (int i=pos; i < str.size(); i++) {
string tmp2(tmp);
tmp2.push_back(str[i]);
cout << tmp2 << endl;
print_comb_utils(str, tmp2, i+1);
}
}
void lexi_combs(string str){
for (int i=0 ; i< str.size(); i++) {
cout << str[i] << endl;
string tmp;
tmp.push_back(str[i]);
print_comb_utils(str, tmp, i+1);
}
}
int main() {
string str;
cin >> str;
lexi_combs(str);
return 0;
}
|
The code just tries to build a recursive structure from the given string. Its assume that the input string has the characters in sorted order else you need to sort the string characters first.
No comments:
Post a Comment