給定一個沒有重復(fù)數(shù)字的序列，返回其所有可能的全排列脂倦。
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
回溯
import copy
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.back_track(res, nums, 0)
return res
def back_track(self, res, nums, n):
if n == len(nums):
temp = copy.deepcopy(nums)
res.append(temp)
else:
for i in range(n, len(nums)):
nums[n], nums[i] = nums[i], nums[n]
self.back_track(res, nums, n+1)
nums[n], nums[i] = nums[i], nums[n]
DFS
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
visited = [0] * len(nums)
res = []
def dfs(path):
if len(path) == len(nums):
res.append(path)
else:
for i in range(len(nums)):
if not visited[i]:
visited[i] = 1
dfs(path + [nums[i]])
visited[i] = 0
dfs([])
return res
