题解 | #火车进站#

//https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26pageSize%3D50%26search%3D50%26tpId%3D37%26type%3D37&difficulty=&judgeStatus=&tags=&title=%E7%81%AB%E8%BD%A6&gioEnter=menu

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

using namespace std;

void dfs(vector<char> in, int index, stack<char> &st, string &out, vector<string> &ans){
    if(index==in.size()&&st.empty()){
        ans.push_back(out);
        return;
    }

    if(index<in.size()){
        st.push(in[index]);
        dfs(in, index+1, st, out, ans);
        st.pop();
    }

    if(!st.empty()){
        out.push_back(st.top());
        st.pop();
        dfs(in, index, st, out, ans);
        st.push(out.back());
        out.pop_back();
    }

}

int main() {
    int n = 0;

    while(cin >> n){
        vector<char> in(n);

        for(int i = 0;i<n;i++){
            cin >> in[i];

            //cout << in[i];

        }

        stack<char> st;
        string out;
        vector<string> ans;

        dfs(in, 0, st, out, ans);

        sort(ans.begin(), ans.end());

        for(auto cstr:ans){
            for(auto cc:cstr)
                cout << cc << " ";
            cout << endl;
        }

    }

}