题解 | #火车进站#

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n;
vector<int> in_order;
vector<vector<int>> all_sequences;

// in_idx: 下一辆要进站的火车在 in_order 中的索引
// station: 当前在站台（栈）中的火车
// current_out: 当前已出站的火车序列
void dfs(int in_idx, stack<int>& station, vector<int>& current_out) {
    // 基线条件：当出站序列满了，说明找到一个完整解
    if (current_out.size() == n) {
        all_sequences.push_back(current_out);
        return;
    }

    // 选择1：出站（如果栈不为空）
    if (!station.empty()) {
        int train_out = station.top();
        station.pop();
        current_out.push_back(train_out);

        dfs(in_idx, station, current_out);

        // 回溯
        current_out.pop_back();
        station.push(train_out);
    }

    // 选择2：进站（如果还有待进站的火车）
    if (in_idx < n) {
        int train_in = in_order[in_idx];
        station.push(train_in);

        dfs(in_idx + 1, station, current_out);

        // 回溯
        station.pop();
    }
}

int main() {
    cin >> n;
    in_order.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> in_order[i];
    }

    stack<int> station;
    vector<int> current_out;
    dfs(0, station, current_out);

    sort(all_sequences.begin(), all_sequences.end());

    for (const auto& seq : all_sequences) {
        for (int i = 0; i < seq.size(); ++i) {
            cout << seq[i] << (i == seq.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    static int n;
    static int[] in_order;
    static List<List<Integer>> all_sequences = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        in_order = new int[n];
        for (int i = 0; i < n; i++) {
            in_order[i] = sc.nextInt();
        }

        dfs(0, new Stack<Integer>(), new ArrayList<Integer>());

        // 对结果进行字典序排序
        Collections.sort(all_sequences, (list1, list2) -> {
            for (int i = 0; i < n; i++) {
                if (!list1.get(i).equals(list2.get(i))) {
                    return list1.get(i) - list2.get(i);
                }
            }
            return 0;
        });

        for (List<Integer> seq : all_sequences) {
            for (int i = 0; i < seq.size(); i++) {
                System.out.print(seq.get(i) + (i == seq.size() - 1 ? "" : " "));
            }
            System.out.println();
        }
    }

    static void dfs(int in_idx, Stack<Integer> station, List<Integer> current_out) {
        if (current_out.size() == n) {
            all_sequences.add(new ArrayList<>(current_out));
            return;
        }

        // 选择1：出站
        if (!station.isEmpty()) {
            int train_out = station.pop();
            current_out.add(train_out);
            dfs(in_idx, station, current_out);
            // 回溯
            current_out.remove(current_out.size() - 1);
            station.push(train_out);
        }

        // 选择2：进站
        if (in_idx < n) {
            int train_in = in_order[in_idx];
            station.push(train_in);
            dfs(in_idx + 1, station, current_out);
            // 回溯
            station.pop();
        }
    }
}

import sys

n = 0
in_order = []
all_sequences = []

# in_idx: 下一辆待进站火车的索引
# station: 栈
# current_out: 当前出站序列
def dfs(in_idx, station, current_out):
    if len(current_out) == n:
        all_sequences.append(list(current_out))
        return

    # 选择1：出站
    if station:
        train_out = station.pop()
        current_out.append(train_out)
        dfs(in_idx, station, current_out)
        # 回溯
        current_out.pop()
        station.append(train_out)

    # 选择2：进站
    if in_idx < n:
        train_in = in_order[in_idx]
        station.append(train_in)
        dfs(in_idx + 1, station, current_out)
        # 回溯
        station.pop()

def main():
    global n, in_order
    lines = sys.stdin.readlines()
    n = int(lines[0])
    in_order = list(map(int, lines[1].split()))
    
    dfs(0, [], [])
    
    all_sequences.sort()
    
    for seq in all_sequences:
        print(*seq)

if __name__ == "__main__":
    main()