|
更多精彩内容，请关注【力扣中等题】。
题目
难度：★★★☆☆
类型：数学
方法：回溯法
题目
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解答
全排列其实可以使用python内置的permutations函数，例如求['a', 'b', 'c']的全排列，可以使用：itertools.permutations(['a', 'b', 'c'],3)快速得到。这里参考了大佬博客。
方案1：回溯法
我们举个例子，以字符串列表['a', 'b', 'c']为例，我们逐个位确定全排列的所有可能。回溯法的原理在于在前n-1位元素确定的情况下，求取n位以后的全排列。本例中，首先固定第0位，就是分别将第0位与它本身及后面各位元素交换，得到3种不同的可能，在固定这一位后，在考虑第1位的可能性，将第1位与它本身及其后元素交换，有两种可能性，当前两位元素确定后，最后一位只有一种可能性。因此一共有6种可能。
将列表的第0位与第0位交换（相当于不变），此时列表变为['a', 'b', 'c']；
1.1 将列表的第1位与第1位交换（相当于不变），得到列表['a', 'b', 'c']；
1.2 将列表的第1位与第2位交换，得到列表['a', 'c', 'b']； 将列表的第0位与第1位交换，得到列表['b', 'a', 'c']；
2.1 将列表的第1位与第1位交换（相当于不变），得到列表['b', 'a', 'c']；
2.2 将列表的第1位与第2位交换，得到列表['b', 'c', 'a']； 将列表的第0位与第2位交换，得到列表['c', 'b', 'a']；
3.1 将列表的第1位与第1位交换（相当于不变），得到列表['c', 'b', 'a']；
3.2 将列表的第1位与第2位交换，得到列表['c', 'a', 'b']
这里需要注意的是，每次交换元素并回溯寻找后，都要将元素交换回来，保持没有交换前的状态。
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def backtrack(position, end):
"""
Find possible results using backtrack.
:param position:
:param end:
:return:
"""
if position == end:
res.append(nums[:])
return
for index in range(position, end):
nums[index], nums[position] = nums[position], nums[index]
backtrack(position + 1, end)
nums[index], nums[position] = nums[position], nums[index]
res = []
backtrack(0, len(nums))
return res
方案2：深度优先搜索
与回溯法类似，增加临时列表用来存储是否查看过变量。
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
visit = [True for _ in range(len(nums))]
tmp = nums[:]
def dfs(position):
if position == len(nums):
res.append(tmp[:])
return
for index in range(0, len(nums)):
if visit[index]:
tmp[position] = nums[index]
visit[index] = False
dfs(position + 1)
visit[index] = True
res = []
dfs(0)
return res
如有疑问或建议，欢迎评论区留言~
|
