@author: ZZQ
@software: PyCharm
@file: permute.py
@time: 2018/11/15 19:42
要求：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
import copy
"""
思路一： DFS，去掉不满足条件的排列
"""
class Solution():
def __init__(self):
pass
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
temp_ans = []
length = len(nums)
cur_length = 0
self.dfs(temp_ans, nums, cur_length, length, ans)
return ans
def dfs(self, temp_ans, nums, cur_length, length, ans):
if cur_length == length:
tt_ans = copy.deepcopy(temp_ans)
ans.append(tt_ans)
else:
for i in range(length):
if nums[i] not in temp_ans:
temp_ans.append(nums[i])
self.dfs(temp_ans, nums, cur_length+1, length, ans)
temp_ans.pop()
"""
思路二： 交换元素+DFS
"""
class Solution2():
def __init__(self):
pass
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums_len = len(nums)
ans = []
if nums_len == 0 or nums == []:
return []
self.exchange(nums, 0, nums_len, ans) # 采用前后元素交换的办法，dfs解题
return ans
def exchange(self, nums, i, len, ans):
if i == len-1: # 将当前数组加到结果集中
temp_list = []
for j in range(len):
temp_list.append(nums[j])
ans.append(temp_list)
return
# 将当前位置的数跟后面的数交换，并搜索解
for j in range(i, len):
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
self.exchange(nums, i+1, len, ans)
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp