题解 | #火车进站#

// mark 一下

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }

            Stack<Integer> stack = new Stack<>();
            List<String> ans = new ArrayList<>();
            // 递归：数组，入栈数，出栈数，一次结果，结果集合，栈。
            trainFunc(a, 0, 0, "", ans, stack);

            Collections.sort(ans);
            for (String each : ans) {
                System.out.println(each);
            }
        }
    }

    public static void trainFunc(int[] a, int pushNum, int popNum, String tmp, 
        List ans, Stack stack) {
        // 1. 出栈数 == 总数 则形成一次结果 一次递归的终止条件
        if (popNum == a.length) {
            ans.add(tmp);
            tmp = "";
        }

        // 2. 入栈数 < 总数 则 继续入栈 然后递归 再出栈 恢复现场
        if (pushNum < a.length) {
            stack.push(a[pushNum]);
            // 入栈数 + 1
            trainFunc(a, pushNum + 1, popNum, tmp, ans, stack);
            stack.pop();
        }

        // 3. 栈 不为 空 则 持续出栈 然后递归 再入栈 恢复现场
        if (!stack.isEmpty()) {
            int x = (int) stack.pop();
            // 出栈的时候就是一个序列的一个元素添加的时候
            tmp = "".equals(tmp) ? String.valueOf(x) : tmp + " " + x;
            // 出栈数 + 1
            trainFunc(a, pushNum, popNum + 1, tmp, ans, stack);
            stack.push(x);
        }
    }
}