题解 | #火车进站II#

// 多行输入
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
const inputArr = [];//存放输入的数据
rl.on('line', function (line) {
    //line是输入的每一行，为字符串格式
    inputArr.push(line.split(' ').map(item => Number(item)));//将输入流保存到inputArr中（用map将字符串数组转为数字）
}).on('close', function () {
   let res = fun(inputArr)//调用函数
   res.forEach(item => console.log(item.join(' '))) //打印结果
})

//解决函数
function fun(arr) {
    let N = arr[0][0];
    let train = arr[1].concat();    //未进站的火车
    let res = [];    //输出的结果
    let station = []    //站台栈内的火车
    let outStation = []    //发出的火车
    let backtrace = (train, station, outStation) => {
        if (outStation.length == N) {
            res.push([...outStation])
            return;
        }
        if (station.length == 0 && train.length != 0) {
            // 如果车站为空且未进站的火车不为空，则进站
            station.push(train.shift())
            backtrace(train, station, outStation)
        } else if (station.length != 0 && train.length == 0) {
            // 如果车站不为空，且没有未进站的火车，则顺序出站
            outStation.push(station.pop())
            backtrace(train, station, outStation)
        } else if (station.length != 0 && train.length != 0) {
            // 如果车站不为空，且还有未进站的火车，则可以选择1.出站，2.进站,并回溯
            let temp1 = [...outStation];
            let temp2 = [...station];
            let temp3 = [...train]
            // 出站
            outStation.push(station.pop())
            backtrace(train, station, outStation)
            // 回溯 
            outStation = temp1;
            station = temp2;
            train = temp3;
            // 进站
            station.push(train.shift())
            backtrace(train, station, outStation)
        }
    }
    backtrace(train, station, outStation)
    return res.sort((a, b) => a.join('') - b.join(''))
}