题解 | #没有重复项数字的全排列#python版

对于一般的组合排列等问题，基本都可以使用回溯算法解决。回溯算法就相当于遍历一棵多叉树，而且它的方式其实非常类似于DFS，都是沿着路径一直遍历到叶子节点为止。这种形式递归肯定是少不了的。

以[1,2,3]为例，我们可以直接将可能的遍历路径画出来：

从图中可以很明显的看到，我们需要一直遍历到叶子节点才会得到需要的一个结果，那么回溯算法的结束条件就是使用完所有数字：

if len(track) == len(num):
    res.append(track[:])
    return

这里的res表示最终结果，包含多个列表；track表示找到的一条路径，特别注意：这里不能直接使用res.append(track)的添加方式。因为这种方式，res中只是存储了track的地址，track中的值一改变，res中包含track的值也会变化，所以我们需要使用track[:]的方式进行添加；而num就是程序的输入。

还有一个重要的点就是不要重复使用数字。对于其他语言，可能最方便的方式就是开一个哈希表进行记录访问过的数字，python会方便一些，直接判断就行，不需要写太复杂的代码：

if num[i] in track:
    continue

完成以上两步之后，其实只要套用回溯算法的套路就行了：

进行选择
回溯
撤销选择

总的参考代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        
        # 最终结果
        res = []
        # 路径
        track = []
        
        def backtrack(track, num):
            # 结束条件
            if len(track) == len(num):
                res.append(track[:])
                return
            
            for i in range(len(num)):
                # 当前数字使用过，使用下一个数字
                if num[i] in track:
                    continue
                # 选择一个数字添加到路径中
                track.append(num[i])
                # 进行回溯
                backtrack(track, num)
                # 撤销当前选择
                track.pop()
        
        backtrack(track, num)
        return res