题解 | #火车进站#

这道题的dfs比较难理解，我认为主要困难的地方在于，进站的时候也要回溯这里，，每次进行dfs之后一定要回到原来的状态。最后用的set来排序。

#include <algorithm>
#include <vector>
#include <stack>
#include <set>

using namespace std;

void dfs(vector<int> &intrain,stack<int>&s,vector<int> output,set<vector<int>> &st,int index){
    if(output.size()==intrain.size()){
        st.insert(output);
        return ;
    }
    for(int i = 0;i<2;i++){
        if(i==0&&!s.empty()){//这里出栈
            int temp = s.top();
            s.pop();
            output.push_back(temp);
            dfs(intrain,s,output,st,index);//dfs后一定要回到原来的状态，
            //像什么都没发生一样,这里理解就想像dfs已经把你要的序列保存起来了。
            output.pop_back();//现在回到原来的状态，准备下一个的进栈
            s.push(temp);
        }
        if(i==1&&(index!=intrain.size()-1)){//这里有的题解的index
        //代表即将要加入的列车序号我这里的代表已经加入到栈的序号。所以
        //当index==intrain.size()-1的时候说明最后一个已经入栈。跳过这里
            index++;
            int temp = intrain[index];
            s.push(temp);
            dfs(intrain,s,output,st,index);
            s.pop();
            index--;
            
            
        }
        
        
    }
    return;//这里要return，就是前面那些不满足条件的返回
    
    
    
    
    
}

int main() {
    int  N;
    while(cin>>N){
      vector<int> intrain;
        for(int i = 0;i<N;i++){
            int temp;
            cin>>temp;
            intrain.push_back(temp);
        }
        set<vector<int>> st;//最后需要字典序
        stack<int> s;//火车的入栈
        s.push(intrain[0]);//默认先把第一辆火车入栈,不然空的是没法输出的。
        int index = 0;//这里就是默认第一个已经进栈
        vector<int> output;//每一个序列的输出
        dfs(intrain,s,output,st,0);
        for(auto it = st.begin();it!=st.end();it++){
            for(int i = 0;i<intrain.size();i++){
                cout<<(*it)[i]<<' ';
                
            }
            cout<<endl;
        }
        
    }
}