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

全排列(num) = 元素i + 全排列(num - i)

[1,2,3]的全排列思路：

• f([])：调用f([1])，[1].pop()，调用f([2])，...，return
• f([1])：调用f([1,2])，[1,2].pop()，调用f([1,3])，...，return
• f([1,2])：调用f([1,2,3])，[1,2,3].pop()，return
• f([1,2,3])：return

import copy
class Solution:
    res = []
    def permute(self , num: List[int]) -> List[List[int]]:
        num.sort()
        mark = [0 for i in range(len(num))]
        arr = []
        self.full_permute(num,arr,mark)
        return Solution.res
    
    def full_permute(self, num, arr, mark):
        if len(arr) == len(num):
            # res.append()添加的是arr的引用，递归结束后，arr==[]，res会全为空
            # 因此需要在新内存中复制一份当前的arr
            Solution.res.append(copy.deepcopy(arr))
        for i in range(len(num)):
            if mark[i] == 0:  # 表示当前元素不在arr中
                arr.append(num[i])
                mark[i] = 1
                self.full_permute(num,arr,mark)
                arr.pop()
                mark[i] = 0