1248 -- 【回溯练习】无重复元素的全排列

#include <iostream>
#include <vector>
#include <algorithm>
 
void generatePermutations(std::vector<char>& letters, std::vector<bool>& used, std::vector<char>& permutation, int n) {
    if (permutation.size() == n) {
        // 输出当前的排列
        static int count = 1;
        std::cout << count++ << ":";
        for (char letter : permutation) {
            std::cout << letter;
        }
        std::cout << std::endl;
        return;
    }
 
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            used[i] = true;
            permutation.push_back(letters[i]);
 
            generatePermutations(letters, used, permutation, n);
 
            used[i] = false;
            permutation.pop_back();
        }
    }
}
 
void generateUniquePermutations(const std::string& str) {
    int n = str.length();
    std::vector<char> letters(str.begin(), str.end());
    std::sort(letters.begin(), letters.end()); // 按照字典顺序排序
    std::vector<bool> used(n, false);
    std::vector<char> permutation;
 
    generatePermutations(letters, used, permutation, n);
}
 
int main() {
    std::string str;
    std::cin >> str;
 
    generateUniquePermutations(str);
 
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
 
void generatePermutations(std::vector<char>& letters, std::vector<bool>& used, std::vector<char>& permutation, int n) {
    if (permutation.size() == n) {
        // 输出当前的排列
        static int count = 1;
        std::cout << count++ << ":";
        for (char letter : permutation) {
            std::cout << letter;
        }
        std::cout << std::endl;
        return;
    }
 
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            used[i] = true;
            permutation.push_back(letters[i]);
 
            generatePermutations(letters, used, permutation, n);
 
            used[i] = false;
            permutation.pop_back();
        }
    }
}
 
void generateUniquePermutations(const std::string& str) {
    int n = str.length();
    std::vector<char> letters(str.begin(), str.end());
    std::sort(letters.begin(), letters.end()); // 按照字典顺序排序
    std::vector<bool> used(n, false);
    std::vector<char> permutation;
 
    generatePermutations(letters, used, permutation, n);
}
 
int main() {
    std::string str;
    std::cin >> str;
 
    generateUniquePermutations(str);
 
    return 0;
}