题解 | #火车进站#

深度优先算法，不设置结束条件，遍历所有情况并保存。

每次递归都要把已出栈的（outs）和未出栈的（stack）复制到新集合中，避免在递归中修改原来的集合。

每次进栈，到达数组最后一个元素，则保存一个结果；不是最后一个元素，两种情况：1. 继续进栈；2.遍历栈中元素出栈，每个元素出栈都要一次递归。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        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<Integer> outs = new ArrayList<>();
        List<String> results = new ArrayList<>();
        dfs(arr, 0, stack, outs, results);
        Collections.sort(results);
        for (int i = 0; i < results.size(); i++) {
            System.out.println(results.get(i));
        }
    }

    private static void dfs(int[] arr, int index, Stack<Integer> stack,
                            List<Integer> outs, List<String> results) {
        Stack<Integer> temp = new Stack<>();
        List<Integer> tempOut = new ArrayList<>();
        for (int i = 0; i < stack.size(); i++) {
            temp.push(stack.get(i));
        }
        temp.push(arr[index]);
        for (int i = 0; i < outs.size(); i++) {
            tempOut.add(outs.get(i));
        }
        if (index == arr.length - 1) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < tempOut.size(); i++) {
                builder.append(tempOut.get(i)).append(" ");
            }
            while (!temp.isEmpty()) {
                builder.append(temp.pop()).append(" ");
            }
            results.add(builder.toString());
        } else {
            dfs(arr, index + 1, temp, tempOut, results);
            while (!temp.isEmpty()) {
                int t = temp.pop();
                tempOut.add(t);
                dfs(arr, index + 1, temp, tempOut, results);
            }
        }
    }
}