华为OD机试 考古学家

题目描述

有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段原地发现n个断口整齐的石碑碎片。为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字 组合数Q，你能帮忙吗?

输入描述

第一行输入n，n表示石碑碎片的个数。

第二行依次输入石碑碎片上的文字内容s，共有n组。

输出描述

输出石碑文字的组合 (按照升序排列Q)，行未无多余空格

用例

输入

abc

输出

abc

acb

bac

bca

cab

cba

#include <bits/stdc++.h>
using namespace std;
vector<vector<char>>result;
void back1(vector<char>path,vector<int> used, vector<char> in,int num) {
    if (path.size() == num) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < num; i++) {
        if (used[i] == 1) {
            continue;
        }
        if (used[i] == 0) {
            path.push_back(in[i]);
            used[i] = 1;
        }
        back1(path,used,in,num);
        path.pop_back();
        used[i] = 0;
    }
}
int main() {
    int num = 0;
    cin >> num;
    vector<char>path;
    vector<char>in;
    vector<int>used(num,0);
    char tmp = {0};
    while (cin >> tmp) {
        in.push_back(tmp);
        if (cin.get() == '\n')
            break;
    }
    back1(path, used, in, num);
    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j];
        }
        cout << endl;
    }
}