题解 | #火车进站#

1. 回溯。
2. base case 要结合 情况判断。

#include<bits/stdc++.h>

using namespace std;


//result:结果集，temp：临时出车路径，arr:入站序列，n：火车数 stack：火车站 i:出栈序列位置 j：入站序列位置
void DFS(vector<vector<int>>& res, vector<int> & temp, vector<int> arr, int n, stack<int>& station , int i, int j){
    //base case
    if(j==n&&i==n){//所有进站得和出站得可能性已经走完了
       res.push_back(temp);
       return;
    }

    //选择进站（入栈序列不为空）:入栈序列不为空，就可以选择。选择之后递归，之后再撤销选择
    if(j!=n){
        station.push(arr[j]);

        DFS(res,temp,arr,n,station,i, j+1);

        station.pop();
    }

     //栈顶的元素出栈：也是可选的(栈不空就可以操作)
    if(!station.empty()){
        int x = station.top();//大回溯选择
        station.pop();

        //出站序列构建
        temp.push_back(x);//选择
        DFS(res,temp,arr,n,station, i+1, j);
        temp.pop_back();//小回溯复原


        //大回溯复原
        station.push(x);

    }

}


int main(){

    int n,a;

    while(cin>>n){
        vector<int> train;

        for(int i=0; i< n; i++){
            cin>>a;
            train.emplace_back(a);
        }
        vector<vector<int>> res;
        vector<int> path;
        stack<int> station;
        DFS(res,path,train,n,station,0,0);

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

        //输出
        for(int i = 0; i < res.size();i++){

            for(int j =0; j< n;j++){
                if(j==n-1){
                    cout<<res[i][j]<<endl;
                }else{
                    cout<<res[i][j]<<" ";
                }

            }
        }


    }

    return 0;
}