Given a collection of distinct integers, return all possible permutations.
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
return [[n]+p
for i, n in enumerate(nums)
for p in self.permute(nums[:i]+nums[i+1:])] or [[]]
1 第一种方法：使用递归，每次固定第一个元素，然后连接上后面元素的全排列，递归下去
2 遍历每一个位置，对每一个位置都从集合中选一个未被选的元素
3 [[]]代表的是nums为空的情况
第二种方法：非递归的方式
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ret = [[]]
for n in nums:
temp = []
for s in ret:
for i in range(len(s)+1):
temp.append(s[:i]+[n]+s[i:])
ret = temp
return ret
1 我们先得到前i个元素的全排列，然后加入第i+1个元素，这个元素可以加入到前面所有排列中，而且对于每一个排列，可以加入到这个排列中的所有位置；由于前i+1个元素的排列是没有重复的，所以加入这个以后，也不会有重复的集合出现
2 使用temp变量记录当前最外层循环下产生的所有排列
3 ret记录之前产生的所有排列
4 for i in range(len(s)+1):这里为什么要遍历到len(s)，因为加入i+1后的长度是len(s)+1
