全排列

1、题目

图1

2、题解

回溯法

可以将问题转换成在一行空格中填入给定的数，回溯法就是一种穷举的算法，从左到右依次填入数字。定义函数back(first，output)，表示从左往右填到第first个位置的排列为output。

• 当first=n，表示已经填完n个位置，找到可行解，将output放入数组，递归结束
• 当first < n，需要考虑当前位置填写的数。根据题目要求不能填入重复的数，可以将给定数组划分成两块，左边表示已经填过的，右边表示待填写的。在递归过程中动态维护该数组。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def back(first=0):
            if first == n:
                #该处必须为nums的拷贝，否则会改变nums数组本身
                ans.append(nums[:])

            for i in range(first,n):
                nums[first], nums[i] = nums[i],nums[first]

                back(first+1)
                nums[first], nums[i] = nums[i],nums[first]

        
        n = len(nums)
        ans=[]
        back()

        return ans