题解 | 全排列

n = int(input())
b = [False] * (n + 1)   # 下标 1~n，所以长度 n+1 更方便
path = []

def dfs():
    if len(path) == n:
        print(' '.join(map(str, path)))
        return
    for i in range(1, n + 1):
        if not b[i]:
            b[i] = True       # 即这个深度放 刚访问的i
            path.append(i)    
            dfs()             # 深度+1，当深度到给出的长度时得到排列
            path.pop()
            b[i] = False      # 再把刚访问的i置为未访问过，下次用

dfs()