题解 | #火车进站#

package main

import (
    "fmt"
    "sort"
)

func permute(in []int, nums []int) [][]int {
    var path []int
    var ans [][]int

    // 标记路径上不能使用重复元素(不是一层上)
    used := make(map[int]bool)

    // 每层都从头开始进行遍历, 所以不需要 start 字段
    backtracking(in, nums, used, path)

    return ans
}

func backtracking(in []int, nums []int, used map[int]bool, path []int) {
    if len(path) == len(nums) {
        if isValid(in, path) {
            print(path)
        }
        return
    }

    for i:=0; i<len(nums); i++ {
        if used[nums[i]] {
            continue
        }

        used[nums[i]] = true
        path = append(path, nums[i])
        backtracking(in, nums, used, path)
        path = path[:len(path)-1]
        used[nums[i]] = false
    }
}

func isValid(in []int, out []int) bool {
    var stk []int

    var index int
    for _, num := range in {
        stk = append(stk, num)
        for len(stk) > 0 && out[index] == stk[len(stk)-1] {
            stk = stk[:len(stk)-1]
            index++
        }
    }

    return len(stk) == 0
}

func print(out []int) {
    for k:=0; k<len(out); k++ {
        fmt.Printf("%d ", out[k])
    }
    fmt.Println()
}

func main() {
    var n int
    fmt.Scan(&n)

    var in []int
    for i:=0; i<n; i++ {
        var num int
        fmt.Scan(&num)
        in = append(in, num)
    }

    nums := make([]int, n)
    copy(nums, in)

    sort.Ints(nums)
    permute(in, nums)
}

// 本题输入为一行整形数字，所以采用：fmt.Scan(&num)