题解 | #火车进站# 相对简单

import java.util.*;
public class Main{
    public static TreeSet<String> res = new TreeSet<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = Integer.valueOf(sc.nextLine());
        String input = sc.nextLine();
        String[] vals = input.split(" ");
        LinkedList<String> ll = new LinkedList<String>();
        LinkedList<String> temp = new LinkedList<String>();
        int i=0,j=0;
        traceBack(vals,ll,temp,i,j);
        printResult();
    }
    //train表示火车站中的火车，in表示进站的计数，out表示出站的计数，ll表示出站的序列
    public static void traceBack(String[] vals,LinkedList<String> ll,LinkedList<String> train,int in,int out){
        int len = vals.length;
        if( in == len && out == len){ 
            StringBuffer sb = new StringBuffer();
            for(int i=0;i<len;i++){
                if(i > 0){
                    sb.append(" ");
                }
                sb.append(ll.get(i));
            }
            res.add(sb.toString());
            return;
        }
        if( in != len){
            train.add(vals[in]);
            traceBack(vals,ll,train,in+1,out);
            train.removeLast();
        }
        if( !train.isEmpty()){
            String mid = train.removeLast();
            ll.add(mid);
            traceBack(vals,ll,train,in,out+1);
            ll.removeLast();
            train.add(mid);
        }
        
    }
    public static void printResult(){
        for(String x: res){
            System.out.println(x);
        }
    }
}