题解 | #火车进站#

import java.util.*;

/**
思路：照搬大佬!!!
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i = 0; i < n; i++){
                arr[i] = in.nextInt();
            } 
            Stack<Integer> stack = new Stack<>();
            List<String> list = new ArrayList<>();
            //采用递归思想
            trainOut(arr,0,0, stack, "", list);
            //结果排序
            Collections.sort(list);
            //输出结果
            for(String s : list){
                System.out.println(s);
            }
        }
    }
    /**
    arr 数据
    input,output 分别为入栈or出栈次数
    stack 出入的栈 
    s 每一种循环的结果
    list 存储所有结果
     */
    private static void trainOut(int[] arr, int input, int output, Stack<Integer> stack, String s, List<String> list){
        //结束条件：全部火车都已出栈，保存出栈结果
        if(output == arr.length){
            list.add(s);
        }
        //右边情况
        if(input < arr.length){
            stack.push(arr[input]);
            //前面i+1个火车已经确定， 通过递归求后面所有情况    
            trainOut(arr,input + 1, output, stack, s, list);
            stack.pop();//溯回 - 即恢复进入循环前的状态
        }


        //中间先出栈，再考虑右边的情况
        if(!stack.isEmpty()){
            int temp = stack.pop();
            trainOut(arr, input, output + 1, stack, s + temp + " ", list);
            stack.push(temp);//溯回
        }
    }
}