火车进站问题等同于括号生成[1]。
 BM60 括号生成。

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为："((()))", "(()())", "(())()", "()()()", "()(())"

 把“(”认为进栈操作，“)”认为出栈操作，就快可以求解火车进站问题。
我的代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
class BitVector{
public:
    BitVector():m_cap(32),m_size(0){}
    void push_back(uint32_t v){
        v=(v&0x0001)<<m_size;
        m_value+=v;
        m_size++;
    }
    uint32_t at(int i){
        uint32_t mask=1<<i;
        uint32_t v=(m_value&mask)>>i;
        return v;
    }
    uint32_t size() const{return m_size;}
    uint32_t m_value=0;
    uint32_t m_cap:16;
    uint32_t m_size:16;
};
static inline void print_flag(BitVector& act){

    for(int i=0;i<act.size();i++){
        if(1==act.at(i)){
            std::cout<<"in"<<" ";
        }else{
            std::cout<<"out"<<" ";
        }
    }
    std::cout<<std::endl;
}
void backTracking(std::vector<BitVector> &actions,
                  BitVector act,int in,int out,
                  int n){
    if(2*n==act.size()){
        actions.push_back(act);
        //print_flag(act);
        return;
    }
    if(in<n){
        BitVector copy=act;
        copy.push_back(1);
        backTracking(actions,copy,in+1,out,n);
    }
    if(out<in){
        BitVector copy=act;
        copy.push_back(0);
       backTracking(actions,copy,in,out+1,n);
    }
}
void postProcessing(BitVector&act,std::vector<int>&train,
                    std::vector<int>& output){
    int index=0;
    std::vector<int> q;
    for(int i=0;i<act.size();i++){
        if(1==act.at(i)){
            q.push_back(train.at(index));
            index++;
        }else{
            int v=q.back();
            q.pop_back();
            output.push_back(v);
        }
    }
}
int main(){
    int n=3;
    std::vector<BitVector> res;
    std::vector<int> train;
    std::vector<int> output;
    std::cin>>n;
    for(int i=0;i<n;i++){
        int v=0;
        std::cin>>v;
        train.push_back(v);
    }
    output.resize(n,0);
    BitVector state;
    backTracking(res,state,0,0,n);
    std::vector<std::vector<int>> comb;
    for(int i=0;i<res.size();i++){
        output.clear();
        postProcessing(res.at(i),train,output);
        comb.push_back(output);
    }
    std::sort(comb.begin(),comb.end(),[](const std::vector<int>& a,const std::vector<int>&b){
        bool ret=false;
        for(int i=0;i<a.size();i++){
            if(a.at(i)==b.at(i)){
                continue;
            }else{
                ret=(a.at(i)<b.at(i));
                break;
            }
        }
        return ret;
    });
    for(int i=0;i<comb.size();i++){
        for(int j=0;j<comb.at(i).size();j++){
            if(comb.at(i).size()-1==j){
                std::cout<<comb.at(i).at(j)<<std::endl;
            }else{
                std::cout<<comb.at(i).at(j)<<" ";
            }
        }
    }
    return 0;
}

 博客[2]的解法，不过不太容易理解。

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
static inline void print_path(const std::vector<int>&path){
    for(int i=0;i<path.size();i++){
        std::cout<<path.at(i)<<" ";
    }
    std::cout<<std::endl;
}
void dfs(std::vector<std::vector<int>>&res,
         std::vector<int>&train,
         std::vector<int>&path,
         std::stack<int>&s,
         int x){
    if(x==train.size()&&s.empty()){
        res.push_back(path);
        //print_path(path);
        return;
    }

    if(x<train.size()){
        s.push(train.at(x));
        //std::cout<<x<<" push "<<train.at(x)<<std::endl;
        dfs(res,train,path,s,x+1);
        //std::cout<<x<<" pop "<<s.top()<<std::endl;
        s.pop();
    }
    if(!s.empty()){
        int num=s.top();
        path.push_back(num);
        s.pop();
        //std::cout<<x<<" pop2 "<<num<<std::endl;
        dfs(res,train,path,s,x);
        //std::cout<<x<<" push2 "<<num<<std::endl;
        s.push(num);
        path.pop_back();
     }
    return;
}
int main(){
    int n=3;
    vector<int> train={1,2,3};
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    std::stack<int> s;
    dfs(result,train,path,s,0);
    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;
    }
    return 0;
}

[1]括号生成-C++递归解法
[2] HJ77火车进站