#include <iostream>
 
void backtrack(int p, int n, char* trace, int* avail) {
    if (p == n) {
        std::cout << trace << '\n';
        return;
    }
    for (int i = 255; i >= 0; --i) {
        if (avail[i] > 0) {
            trace[p] = 127 - i;
            avail[i]--;
            backtrack(p+1, n, trace, avail);
            avail[i]++;
        }
    }
}
 
void permuteString(int n, char* str) {
    char* trace = new char[n+1]();
    int* avail = new int[256]();
    for (int i = 0; i < n; ++i) {
        avail[127 - str[i]]++;
    }
    backtrack(0, n, trace, avail);
    delete[] avail;
    delete[] trace;
}
 
int main() {
    int n;
    char* str;
    std::cout << "Enter n: ";
    std::cin >> n;
    str = new char[n+1]();
    std::cout << "Enter string: ";
    std::cin.ignore(1000, '\n');
    std::cin.get(str, n+1, '\n');
 
    permuteString(n, str);
 
    delete[] str;
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdm9pZCBiYWNrdHJhY2soaW50IHAsIGludCBuLCBjaGFyKiB0cmFjZSwgaW50KiBhdmFpbCkgewogICAgaWYgKHAgPT0gbikgewogICAgICAgIHN0ZDo6Y291dCA8PCB0cmFjZSA8PCAnXG4nOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGZvciAoaW50IGkgPSAyNTU7IGkgPj0gMDsgLS1pKSB7CiAgICAgICAgaWYgKGF2YWlsW2ldID4gMCkgewogICAgICAgICAgICB0cmFjZVtwXSA9IDEyNyAtIGk7CiAgICAgICAgICAgIGF2YWlsW2ldLS07CiAgICAgICAgICAgIGJhY2t0cmFjayhwKzEsIG4sIHRyYWNlLCBhdmFpbCk7CiAgICAgICAgICAgIGF2YWlsW2ldKys7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHBlcm11dGVTdHJpbmcoaW50IG4sIGNoYXIqIHN0cikgewogICAgY2hhciogdHJhY2UgPSBuZXcgY2hhcltuKzFdKCk7CiAgICBpbnQqIGF2YWlsID0gbmV3IGludFsyNTZdKCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgIGF2YWlsWzEyNyAtIHN0cltpXV0rKzsKICAgIH0KICAgIGJhY2t0cmFjaygwLCBuLCB0cmFjZSwgYXZhaWwpOwogICAgZGVsZXRlW10gYXZhaWw7CiAgICBkZWxldGVbXSB0cmFjZTsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgbjsKICAgIGNoYXIqIHN0cjsKICAgIHN0ZDo6Y291dCA8PCAiRW50ZXIgbjogIjsKICAgIHN0ZDo6Y2luID4+IG47CiAgICBzdHIgPSBuZXcgY2hhcltuKzFdKCk7CiAgICBzdGQ6OmNvdXQgPDwgIkVudGVyIHN0cmluZzogIjsKICAgIHN0ZDo6Y2luLmlnbm9yZSgxMDAwLCAnXG4nKTsKICAgIHN0ZDo6Y2luLmdldChzdHIsIG4rMSwgJ1xuJyk7CgogICAgcGVybXV0ZVN0cmluZyhuLCBzdHIpOwoKICAgIGRlbGV0ZVtdIHN0cjsKCiAgICByZXR1cm4gMDsKfQ==

NgphYWJiY2M=

6
aabbcc