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

#纠正官方答案python中的错误
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
    def permute(self, num: List[int]) -> List[List[int]]:
        # 先按字典序排序
        num.sort()
        res = list(list())
        # 递归获取
        self.recursion(res, num, 0)
        return res

    # write code here
    def recursion(self, res, num, index):
        # 分枝进入结尾，找到一种排列
        if index == len(num) - 1:
            # k = num.copy() #官方答案还有一个错误的地方是res.append()的是同一个num地址，导致最后答案res里面元素都是一样的
			#后面的改动同时让这里不需要copy()了，因为切片的同时已经重新创建了一个列表
            res.append(num)
        else:
            # 遍历后续的元素
            for i in range(index, len(num)):
                # 交换二者
				#这里是与官方答案不同的地方，交换的是一个元素与它前面的元素列 而不是两个元素 这样能保证后面的元素列一直是字典序
				#num可以分解为num[:index] + num[index:i] + [num[i]] + num[i + 1 :] 交换第二和第三个
                num = num[:index] + [num[i]] + num[index:i] + num[i + 1 :]
                # 继续往后找
                self.recursion(res, num, index + 1)
                # 回溯
                num = num[:index] + num[index + 1 : i + 1] + [num[index]] + num[i + 1 :]