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

from re import template
# T,
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
from itertools import permutations


class Solution:
    # 法2:递归+回溯法
    def recursion(self, res: List[List[int]], num: List[int], index: int):
        # 分支进入结尾，找到一种排列:
        if index == len(num) - 1:
            res.append(num.copy())
            #直接将num添加到结果列表res中，这会导致res中存储的都是对num的引用。
            #当num在回溯过程中发生改变时，res中的所有排列也会相应改变，
            #最终res中的所有元素都会变成相同的最终排列状态。
            #将num的当前状态复制一份再添加到res中。
        else:
            for i in range(index, len(num)):
                # 将index位分别与其后面位置互换
                temp = num[i]
                num[i] = num[index]
                num[index] = temp
                # 继续往后找index+1位置互换情况
                self.recursion(res, num, index + 1)

                # 回溯
                temp = num[i]
                num[i] = num[index]
                num[index] = temp

    def permute(self, num: List[int]) -> List[List[int]]:
        # write code here
        # 法1:函数法
        # res = []
        # for i in permutations(num):#可以对集合或字符串进行排序或排列的所有可能的组合。
        #     res.append(i)

        # return res

        # 法2：递归+回溯法
        num.sort()
        res = list(list())
        self.recursion(res, num, 0)
        res.sort()#保证排列顺序正确
        return res