题解 | #火车进站#

//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>

using namespace std;

class Solution{
public:
    void backtrack(int layer){

//        cout << "layer:" << layer << endl;
//
//        cout << "flag:";
//        for(const int &i:flag)
//            cout << i;
//        cout << endl;
//
//        cout << "_flag:";
//        for(const int &i:_flag)
//            cout << i;
//        cout << endl;
//
//        cout << tem <<endl;


        if(layer==n){
            ans.push_back(tem);
        }
        else
            for(int i = 0;i<n;i++){
                if(layer==0){
                    tem.push_back(num[i]);  //string¿Épush_back char
                }
                else
                    if(_flag[i]==1){
                        tem.push_back(num[i]);
                    }
                if(tem.size()==layer+1){    //size()返回值类型为ll
                    flag[i] = 1;
                    _flag.assign(n, 0);
                    for(int j = i-1;j>=0;j--){
                            if(flag[j]!=1){
                                _flag[j]=1;
                                break;
                            }

                        }
                    for(int j = i+1;j<n;j++)    //逻辑运算提前有风险，可能会提前结束循环
                            if(flag[j]!=1)
                                _flag[j]=1;

                    backtrack(layer+1); //回溯法注意不要改变层数的值

                    tem.pop_back();
                    flag[i] = 0;
                    _flag.assign(n, 0);
                    if(layer!=0){
                    int tag = find(num.begin(), num.end(), tem.back())-num.begin();
                    for(int j = tag-1;j>=0;j--){
                            if(flag[j]!=1){
                                _flag[j]=1;
                                break;
                            }
                        }
                    for(int j = tag+1;j<n;j++)
                            if(flag[j]!=1)
                                _flag[j]=1;

//                    cout << "!!flag:";
//        for(const int &i:flag)
//            cout << i;
//        cout << endl;
//
//        cout << "!!_flag:";
//        for(const int &i:_flag)
//            cout << i;
//        cout << endl;
//        cout << tem <<endl;

                    }
                }
        }

    }

    Solution(int _n){
        n = _n;
        num.resize(n, 0);
        flag.resize(n, 0);
        _flag.resize(n, 0);

        for(int i = 0;i<n;i++)
            cin >> num[i];
    }

    void out(){
        sort(ans.begin(), ans.end());
        for(const string &s:ans){
            for(const char &c:s)
                cout << c << ' ';
            cout << endl;

        }
    }

private:
    vector<string> ans;
    vector<char> num;
    vector<int> flag;
    vector<int> _flag;
    string tem;
    int n = 0;

};

int main() {
    int n = 0;

    while(cin >> n){
        Solution s(n);
        s.backtrack(0);
        s.out();
    }

}