46. 全排列(medium)

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

• show the code:

    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]
        res = []
        for i,num in enumerate(nums):
            for p in self.permute(nums[:i]+nums[i+1:]):
                res.append([num]+p)
        return res

• 此题的关键是要理解全排列生成思想，即递归。
• 我们要求一个数组全部排列的可能性，可以考虑将数组分为两部分：一部分是数组的第一个元素；另一部分是第一个元素以后的所有元素。关于第一个元素，我们可以拿后面的元素和它逐个交换，关于第二部分的元素，我们同样将其分为两部分：第一个数和之后的数。
• 从上面容易看出这是典型的递归思路，在上述代码中，我们遍历数组中每一个元素，将每一个元素放在第一个位置后，再求剩余元素的全排列，这时剩余元素的全排列就可以用递归来解决了，剩余元素具体体现为nums[:i]+nums[i+1:]
• 另外这里要注意递归出口，当nums为空时，需要返回一个二维空数组。
• 可以将上述代码修改为列表表达式，一行就可以解决问题（这个代码也真是niubility，关键在那个or [[]]如果没有的话只会返回[]）：

    def permute(self, nums: List[int]) -> List[List[int]]:
        return [[num]+p for i,num in enumerate(nums) for p in self.permute(nums[:i]+nums[i+1:])] or [[]]

• 关于为什么要有or [[]]的原因，我大概试了一下[] or [[]] >>> [[]] 所以为了避免我们返回[]之后递归就中止了，我们需要设立一个base case即[[]]（其实有点相当于第一种代码里的递归出口）