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個元素的排列是沒有重復的，所以加入這個以后，也不會有重復的集合出現(xiàn)
2 使用temp變量記錄當前最外層循環(huán)下產(chǎn)生的所有排列
3 ret記錄之前產(chǎn)生的所有排列
4?for i in range(len(s)+1):這里為什么要遍歷到len(s)，因為加入i+1后的長度是len(s)+1
