题解 | #火车进站#

#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

void dfs(vector<int>& in_seq, stack<int>& station, vector<int>& out_seq, set<string>& result, int pos) {
    if (pos == in_seq.size() && station.empty()) {
        string s;
        for (int i = 0; i < out_seq.size(); i++) {
            if (i > 0) s += " ";
            s += to_string(out_seq[i]);
        }
        result.insert(s);
        return;
    }
    
    // 选择让火车进站
    if (pos < in_seq.size()) {
        station.push(in_seq[pos]);
        dfs(in_seq, station, out_seq, result, pos + 1);
        station.pop();
    }
    
    // 选择让火车出站
    if (!station.empty()) {
        int temp = station.top();
        station.pop();
        out_seq.push_back(temp);
        dfs(in_seq, station, out_seq, result, pos);
        out_seq.pop_back();
        station.push(temp);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    stack<int> station;
    vector<int> out_seq;
    set<string> result;
    
    dfs(nums, station, out_seq, result, 0);
    
    for (const string& s : result) {
        cout << s << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    private static void dfs(int[] in_seq, Stack<Integer> station, List<Integer> out_seq, 
                          Set<String> result, int pos) {
        if (pos == in_seq.length && station.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < out_seq.size(); i++) {
                if (i > 0) sb.append(" ");
                sb.append(out_seq.get(i));
            }
            result.add(sb.toString());
            return;
        }
        
        // 选择让火车进站
        if (pos < in_seq.length) {
            station.push(in_seq[pos]);
            dfs(in_seq, station, out_seq, result, pos + 1);
            station.pop();
        }
        
        // 选择让火车出站
        if (!station.isEmpty()) {
            int temp = station.pop();
            out_seq.add(temp);
            dfs(in_seq, station, out_seq, result, pos);
            out_seq.remove(out_seq.size() - 1);
            station.push(temp);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Stack<Integer> station = new Stack<>();
        List<Integer> out_seq = new ArrayList<>();
        Set<String> result = new TreeSet<>();
        
        dfs(nums, station, out_seq, result, 0);
        
        for (String s : result) {
            System.out.println(s);
        }
    }
}

def dfs(in_seq, station, out_seq, result):
    if not in_seq and not station:  # 所有火车都已经出站
        result.add(' '.join(map(str, out_seq)))
        return
    
    # 选择让火车进站
    if in_seq:
        station.append(in_seq[0])
        dfs(in_seq[1:], station, out_seq, result)
        station.pop()
    
    # 选择让火车出站
    if station:
        out_seq.append(station[-1])
        temp = station.pop()
        dfs(in_seq, station, out_seq, result)
        station.append(temp)
        out_seq.pop()

def solve(n, nums):
    result = set()
    dfs(nums, [], [], result)
    return sorted(result)

# 处理输入
n = int(input())
nums = list(map(int, input().split()))

# 获取所有可能的出站序列并输出
for seq in solve(n, nums):
    print(seq)