creatingstrings.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> results;
string S;
vector<bool> used;

void backtrack(string& path) {
    if (path.size() == S.size()) {
        results.push_back(path);
        return;
    }

    for (int i = 0; i < S.size(); ++i) {
        if (used[i]) continue;

        // Skip duplicates
        if (i > 0 && S[i] == S[i-1] && !used[i-1]) continue;

        used[i] = true;
        path.push_back(S[i]);
        backtrack(path);
        path.pop_back();
        used[i] = false;
    }
}

int main() {
    cin >> S;
    sort(S.begin(), S.end());  // Required to skip duplicates correctly
    used.resize(S.size(), false);

    string path;
    backtrack(path);

    cout << results.size() << '\n';
    for (string& perm : results) {
        cout << perm << '\n';
    }

    return 0;
}