题解 | #火车进站#

import java.util.*;
public class Main{

    static int[] train;
    static String res;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            train = new int[n];
            res = new String();
            for(int i=0; i<n; i++){
                train[i] = in.nextInt();
            }
            List<String> list = new ArrayList<>();
            Stack<Integer> stack = new Stack<>();
            out(stack, 0, n, list);
            Collections.sort(list, new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s1.compareTo(s2);
                }
            });
            Iterator<String> it = list.listIterator();
            while(it.hasNext()){
                System.out.println(it.next());
            }
        }
    }

    public static void out(Stack<Integer> stack, int index, int n, List<String> list){
        if(index == n&&stack.isEmpty()){
            list.add(new String(res));
            return;
        }
        if(stack.isEmpty()){
            stack.push(train[index++]);
            out(stack, index, n, list);
            stack.pop();
        }else{
            int temp = stack.pop();
            res += temp + " ";
            out(stack, index, n, list);
            res = res.substring(0, res.length()-2);
            stack.push(temp);
            if(index < n){
                stack.push(train[index++]);
                out(stack, index, n, list);
                stack.pop();
            }

        }
    }
}