46、全排列

基本思想：

回溯算法

具体实现：

1.轮流让数组中的每个数当第一个数,交换实现--nums[first], nums[i] = nums[i], nums[first]

这个数nums[first]提出来以后，

再全排列后面的数nums[first+1,:]----递归backtrack(first + 1)

2、递归完以后还要把交换过的位置还原，

比如，2当过第一个数了，接下来该3当第一个数了

就要先把2放回原位，再把3弄出来

nums[first], nums[i] = nums[i], nums[first]

3、递归结束条件

要全排列的数组中没有数了

first == n

代码：

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # 所有数都填完了
            if first == n:  
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack()
        return res