พิมพ์ Combinations ทั้งหมดของสตริงในลำดับ Lexicographical ใน C++

ในปัญหานี้ เราจะได้รับสตริง str และต้องพิมพ์ combinations ทั้งหมดของตัวอักษรในลำดับ lexicographical

ตัวอย่างเพื่อความเข้าใจ

Input: str = 'XYZ'
Output: X XY XYZ XZ XZY Y YX YXZ YZ YZX Z ZX ZXY ZY ZYX

เพื่อแก้ปัญหานี้ เราจะพิมพ์ combinations ทั้งหมดของตัวอักษรในสตริง สำหรับนี้ เราต้องใช้ map data structure เพื่อเก็บตัวอักษรของสตริง สำหรับการ implement เราจะต้องใช้ backtracking เพื่อติดตาม combinations ทั้งหมด

โปรแกรมตัวอย่าง

#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;
}

ผลลัพธ์

The combination of characters of the string -

A AB ABC AC ACB B BA BAC BC BCA C CA CAB CB CBA