## Description

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]


## Solutions

### 1. Backtracking

这里采用了 visited 的方式记录已经访问过的元素，需要回溯！只是通过记录已经遍历过的下标还是不够的。

# Time: O(n^k)
# Space: O(n)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
res = []
visited = set()
self.dfs(nums, visited, [], res)
return res

def dfs(self, nums, visited, path, res):
if not nums:
return

n = len(nums)
if len(path) == n:
res.append(path)
return

for i in range(n):
if nums[i] in visited:
continue
self.dfs(nums, visited, path + [nums[i]], res)
visited.remove(nums[i])
# 25/25 cases passed (36 ms)
# Your runtime beats 96.9 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)


### 2. Backtracking-每次交换两个数

参考了这篇博文解法二的交换两个数的方式进行全排列，结果发现如果用 Python 每次都会修改所有的 nums 对应的值，后来发现需要在 nums 后面加上 copy() 即可。

# Time: O(n^k)
# Space: O(n)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
res = []
self.dfs(nums, 0, res)
return res

def dfs(self, nums, start, res):
if not nums:
return
n = len(nums)
if start >= n:
# res.append(nums)
res.append(nums.copy())
return

for i in range(start, n):
nums[start], nums[i] = nums[i], nums[start]
self.dfs(nums, start+1, res)
nums[start], nums[i] = nums[i], nums[start]


还有一种写法：

class Solution:
def DFS(self, nums, result, current):
if len(nums) == 0:
result.append(current)
return
for i in range(len(nums)):
# current.append(nums[i])
# del nums[i]
# self.DFS(nums, result, current)
temp = nums[0:i] + nums[i+1:]
self.DFS(temp, result, current+[nums[i]])

def permute(self, nums: List[int]) -> List[List[int]]:
result = []
self.DFS(nums, result, [])
return result


### 3. 迭代-交换两个数

"""Time and space complexity are both O(n*(n!)).
Space: It doesn't alloc any extra space, just copy and concat the buffers to form the output. There is n! output and each has n elements.
And
Time: it doesn't do any extra computation but consider needing copy NN! elements. So time complexity is also O(NN!)"""
class Solution:
def permute(self, nums):
ans = [[]]

for n in nums:
temp=[]
for lst in ans:
for i in range(len(lst)+1):
temp.append(lst[:i]+[n]+lst[i:])
ans = temp
return ans