Trong bài toán này, chúng ta được cung cấp chuỗi str và chúng ta phải in tất cả các kết hợp của các ký tự theo thứ tự từ vựng.
Hãy lấy một ví dụ để hiểu rõ vấn đề hơn -
Input: str = ‘XYZ’ Output : X XY XYZ XZ XZY Y YX YXZ YZ YZX Z ZX ZXY ZY ZYX
Để giải quyết vấn đề này, chúng tôi sẽ in tất cả các tổ hợp ký tự trong chuỗi. Đối với điều này, chúng ta cần một cấu trúc dữ liệu bản đồ để lưu trữ các ký tự của chuỗi. Để triển khai, chúng tôi sẽ cần sử dụng backtracking để theo dõi tất cả các kết hợp.
Ví dụ
#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;
} Đầu ra
Sự kết hợp của các ký tự của chuỗi -
A AB ABC AC ACB B BA BAC BC BCA C CA CAB CB CBA