इस समस्या में, हमें स्ट्रिंग स्ट्र दिया जाता है, और हमें वर्णों के सभी संयोजनों को एक लेक्सिकोग्राफ़िक क्रम में प्रिंट करना होता है।
आइए समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
Input: str = ‘XYZ’ Output : X XY XYZ XZ XZY Y YX YXZ YZ YZX Z ZX ZXY ZY ZYX
इस समस्या को हल करने के लिए, हम स्ट्रिंग में वर्णों के सभी संयोजनों को प्रिंट करेंगे। ऐसा करने के लिए, हमें स्ट्रिंग के पात्रों को संग्रहीत करने के लिए एक मानचित्र डेटा संरचना की आवश्यकता होती है। कार्यान्वयन के लिए, हमें सभी संयोजनों पर नज़र रखने के लिए बैकट्रैकिंग का उपयोग करना होगा।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void printResult(char* result, int len);
void findstringCombination(char result[], char str[], int count[],int level, int
size, int length) ;
void printCharCombination(string str);
int main(){
string str = "ABC";
cout<<"The combination of characters of the string :\n";
printCharCombination(str);
return 0;
}
void findstringCombination(char result[], char str[], int count[],int level, int size, int length){
if (level == size)
return;
for (int i = 0; i < length; i++) {
if (count[i] == 0)
continue;
count[i]--;
result[level] = str[i];
printResult(result, level);
findstringCombination(result, str, count, level + 1, size, length);
count[i]++;
}
}
void printCharCombination(string str){
map<char, int> mp;
for (int i = 0; i < str.size(); i++) {
if (mp.find(str[i]) != mp.end())
mp[str[i]] = mp[str[i]] + 1;
else
mp[str[i]] = 1;
}
char* input = new char[mp.size()];
int* count = new int[mp.size()];
char* result = new char[str.size()];
map<char, int>::iterator it = mp.begin();
int i = 0;
for (it; it != mp.end(); it++) {
input[i] = it->first;
count[i] = it->second;
i++;
}
int length = mp.size();
int size = str.size();
findstringCombination(result, input, count, 0, size, length);
}
void printResult(char* result, int len){
for (int i = 0; i <= len; i++)
cout<<result[i];
cout<<endl;
} आउटपुट
स्ट्रिंग के वर्णों का संयोजन -
A AB ABC AC ACB B BA BAC BC BCA C CA CAB CB CBA