用回溯法解决全排列问题

回溯搜索是深度优先搜索（DFS）的一种，回溯法通俗的将其采用的思想是“一直向下走，走不通就掉头”，类似于树的先序遍历。
dfs和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。
由于回溯法花费时间较长，所以对于没有明确的动态规划（DP）和递归解法的或问题要求满足某种性质（约束条件）的所有解或最优解时，才考虑使用回溯法。

# 核心代码
def main():
    global path # 记录路径
    global flag # 标记数组 标记结点是否访问过
    global n
    n = 3 # 全排列 1-3
    path = [-1]*100
    flag = [False]*100
    dfs(0) # 从起点为0的路径开始遍历

def dfs(u):
    if u == n :
        print(path[:n])
        return
    # 排列 1-n
    for idx in range(1,n+1):
        if flag[idx] != True:
            path[u] = idx
            flag[idx] = True
            dfs(idx+1)
            flag[idx] = False # 回溯从初始状态