基本思路

递归，每个位置有n种可能，使用一个数组标记数值i是否被使用过，没有使用过则在位置loc上放置数值i，然后继续考虑下一个位置。

注意递归回溯时要恢复现场。

# 递归
def DFS(loc): # 确定第loc个位置的数
    if loc > n:
        # 打印方案顺序
        for i in range(1, n+1):
            print(st[i], end=' ')
        print()
        return

    for i in range(1,n+1): # 从小到大依次寻找每种可能
        if not use[i]: # 如果位置i的元素没有被使用过
            st[loc] = i # 每一个位置都有n种可能
            use[i] = True # 注意为use数组的元素修改值
            DFS(loc+1)
            st[loc] = 0 # 恢复现场
            use[i] = False


n = int(input())
st = [0]*(n+1) # n个位置的状态数组
use = [False]*(n+1) # use[i]表示数i是否已经被使用过了
DFS(1)