|
更多精彩內容，請關注【力扣中等題】。
題目
難度：★★★☆☆
類型：數學
方法：回溯法
題目
給定一個沒有重復數字的序列，返回其所有可能的全排列。
示例
輸入: [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
如有疑問或建議，歡迎評論區留言~
|
