题解 | 全排列

package main

import (
	"fmt"
	"strconv"
	"strings"
)

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

	// 用于存储当前的排列结果
	path := make([]int, n)
	// 记录数字是否被使用过
	used := make([]bool, n+1)

	// 使用回溯法生成排列
	var backtrack func(int)
	backtrack = func(row int) {
		// 终止条件：已经填满了 n 个位置
		if row == n {
			// 将 path 转为字符串输出，提高效率
			result := make([]string, n)
			for i, v := range path {
				result[i] = strconv.Itoa(v)
			}
			fmt.Println(strings.Join(result, " "))
			return
		}

		// 字典序：从 1 到 n 尝试
		for i := 1; i <= n; i++ {
			if !used[i] {
				used[i] = true
				path[row] = i // 放入当前位置
				backtrack(row + 1)
				used[i] = false // 回溯：撤销选择
			}
		}
	}

	backtrack(0)
}