给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [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即[[]]（其实有点相当于第一种代码里的递归出口）
