给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
记录一下自己的思路总结，关于去重复的思路比较棒：
全排序一：
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
全排序
"""
self.result = []
self.permutation(nums,0)
# print(self.result)
# st = {tuple(i) for i in self.result}
# l = [list(i) for i in st]
return self.result
def permutation(self,nums,start):
length = len(nums)
if start == length-1:
# print(nums)
n = nums[:]
self.result.append(n)
for i in range(start,length):
nums = self.swap(nums,start,i)
self.permutation(nums,start+1)
nums = self.swap(nums,start,i)
def swap(self,l,start,end):
l[start],l[end] = l[end],l[start]
return l
全排序二：
有两种方式，更好的肯定是从底层就不交换大大节约时间，无脑的则是先全排列，后集合去重。
class Solution(object):
def permuteUnique(self, nums):
"""
全排列2集合去重复
:type nums: List[int]
:rtype: List[List[int]]
"""
self.result = []
self.permutation(nums,0)
# print(self.result)
st = {tuple(i) for i in self.result}
l = [list(i) for i in st]
return l
def permutation(self,nums,start):
length = len(nums)
if start == length-1:
# print(nums)
n = nums[:]
self.result.append(n)
for i in range(start,length):
nums = self.swap(nums,start,i)
self.permutation(nums,start+1)
nums = self.swap(nums,start,i)
def swap(self,l,start,end):
l[start],l[end] = l[end],l[start]
return l
class Solution(object):
def permuteUnique(self, nums):
"""
全排列2优化
:type nums: List[int]
:rtype: List[List[int]]
"""
self.result = []
self.permutation(nums,0)
# print(self.result)
return self.result
def permutation(self,nums,start):
length = len(nums)
if start == length-1:
# print(nums)
n = nums[:]
self.result.append(n)
temp = []
for i in range(start,length):
if nums[i] not in temp:
temp.append(nums[i])
nums = self.swap(nums,start,i)
self.permutation(nums,start+1)
nums = self.swap(nums,start,i)
def swap(self,l,start,end):
l[start],l[end] = l[end],l[start]
return l