题解 | #火车进站#

import java.util.*;

// 思路：主要思想是递归，之所以产生很多方案的原因就是，每次进来一辆火车后，我们将其压入栈中，然后我们可以有两种选择，一是不弹出，二是弹出；
// 对于第二种弹出元素，弹出的个数的范围取决于当前栈中元素的个数，所以遍历每种情况，在遍历每种情况的时候再递归到下一辆火车
public class Main {
    static Deque<Integer> stack;
    static int[] nums, outNums;
    static int n;
    static List<String> res;
    public static void main(String[] args) {
        // 完成输入
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        nums = new int[n];
        for (int i=0; i<n; i++) nums[i] = in.nextInt();
        // outNums是用来记录当前递归中，已经出站的火车编号； stack是记录当前车站中还有哪些火车； 
        // res是记录所有结果并进行排序，因为题目要求所有方案以字典序排序输出，所以没办法必须加
        outNums = new int[n];
        stack = new LinkedList<>();
        res = new ArrayList<>();
        // 开始遍历
        dfs(0, 0);
        // 对所有方案排序，并输出
        Collections.sort(res);
        for (String str:res) System.out.println(str);
    }
    
    // i代表已经递归到了第i辆火车，cnt代表已经已经出站的火车数量，即是outNums的下标
    public static void dfs(int i, int cnt) {
        // 这个tmp栈很重要，这是保证dfs返回时，stack中的元素和进来时一样
        Deque<Integer> tmp = new LinkedList<>();
        // 压入当前火车
        stack.push(nums[i]);
        
        // 当递归到最后一辆火车时，我们只需要将其压入栈中，这时所能做的只有弹出栈中所有元素，并将其添加到outNums数组中
        if (i==n-1) {
            
            // 弹出栈中所有元素
            while (stack.size() > 0) {
                tmp.push(stack.peek());
                outNums[cnt++] = stack.pop();
            }
            // 这里>1是因为stack中本身不含有nums[i]
            while (tmp.size() > 1) stack.push(tmp.pop());
            // 将当前方案以字符串形式保存到res中
            StringBuilder sb = new StringBuilder();
            for (int outNum:outNums) sb.append(outNum).append(" ");
            res.add(sb.toString());
        }
        // 如果没有递归到最后一辆火车，那么在将当前火车编号压入栈后，有很多选择，这也就产生了很多方案
        // 一种就是继续压；还有一种就是开始弹出元素，弹出元素个数范围是[0, size]（包含两边界），那么就需要依次遍历
        else {
            int size = stack.size();
            // 继续压
            dfs(i+1, cnt);
            // 开始弹出元素
            for (int j=0; j<size; j++) {
                tmp.push(stack.peek());
                outNums[cnt++] = stack.pop();
                dfs(i+1, cnt);
            }
            // 这里>1是因为stack中本身不含有nums[i]，
            while (tmp.size() > 1) stack.push(tmp.pop());
        }
    }
}