题解 | #火车进站#

import java.util.; import java.io.;

public class Main {

public static void main(String[] args) throws Exception{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    String[] strs = bf.readLine().split(" ");
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(strs[i]);
    }
    // outNums是用来记录当前递归中，已经出站的火车编号；
    int[] outNums= new int[n];
    //stack是记录当前车站中还有哪些火车；
    Deque<Integer> stack = new LinkedList<>();
    //res是记录所有结果并进行排序
    List<String> res = new ArrayList<>();
    // 开始遍历
    dfs(0, 0, stack,nums, n,outNums, res);
    // 对所有方案排序，并输出
    Collections.sort(res);
    for (String str:res) System.out.println(str);
}

// i代表已经递归到了第i辆火车，cnt代表已经已经出站的火车数量，即是outNums的下标
public static void dfs(int i, int cnt,Deque<Integer> stack,int[] nums, int n,int[] outNums, List<String> res) {
    Deque<Integer> tmp = new LinkedList<>(); // 这个tmp栈很重要，这是保证dfs返回时，stack中的元素和进来时一样
    stack.push(nums[i]); // 压入当前火车
    // 当递归到最后一辆火车时，这时所能做的只有弹出栈中所有元素，并将其添加到outNums数组中
    if (i==n-1) {
        while (stack.size() > 0) {// 弹出栈中所有元素
            tmp.push(stack.peek());
            outNums[cnt++] = stack.pop();
        }
        while (tmp.size() > 1) {//这里>1是因为stack中本身不含有nums[i]
            stack.push(tmp.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (int outNum:outNums) sb.append(outNum).append(" ");
        res.add(sb.toString());// 将当前方案以字符串形式保存到res中
    }
    // 如果没有递归到最后一辆火车，那么在将当前火车编号压入栈后，有很多选择，这也就产生了很多方案
    // 一种就是继续压；还有一种就是开始弹出元素，弹出元素个数范围是[0, size]（包含两边界），那么就需要依次遍历
    else {
        int size = stack.size();
        // 继续压
        dfs(i+1, cnt,stack, nums,n,outNums, res);
        // 开始弹出元素
        for (int j=0; j<size; j++) {
            tmp.push(stack.peek());
            outNums[cnt++] = stack.pop();
            dfs(i+1, cnt,stack, nums,n,outNums, res);
        }
        // 这里>1是因为stack中本身不含有nums[i]，
        while (tmp.size() > 1) stack.push(tmp.pop());
    }
}

}