46. 全排列
題目來源：https://leetcode-cn.com/problems/permutations/
題目
給定一個 沒有重復 數字的序列，回傳其所有可能的全排列，
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解題思路
思路：深度優化搜索
先看題目，以所給陣列 [1, 2, 3] 的全排列為例：
- 以 1 開始，全排列有：[1,2,3], [1,3,2]；
- 以 2 開始，全排列有 [2,1,3], [2,3,1]；
- 以 3 開始，全排列有 [3,1,2], [3,2,1]，
從上面的情況，可以看出，列舉每個每一位可能出現的情況，已選擇的數字在下面的選擇則不能出現，按照這個做法，所有的情況將能夠羅列出來，這里其實就是執行一次深度優先搜索，從根節點到葉子節點形成的路徑就是一個全排列，
按照這種思路，沿用上面的例子，從空串列 [] 開始，以 1 開始為例，現在確定以 1 開始，則串列為 [1]，現在選擇 [2] 和 [3] 之中的一個，先選 2，最后剩下的只有數字 3，所以形成全排列 [1, 2, 3]，
已知還有一種情況，也就是 [1, 3, 2]，那么如何實作從 [1, 2, 3] 到 [1, 3, 2] 的變化，深度優先搜索是如何實作的？其實是從 [1, 2, 3] 回到 [1, 2] 的情況，撤銷數字 3，因為當前層只能選擇 3，所以再撤銷 2 的選擇，這樣后面的程式則能在選擇 3 的時候后續也能選擇 2，
代碼實作
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def _dfs(nums, depth, pmt, be_selected, length, ans):
# 表示深度優化搜索的深度等于陣列長度時，這個時候表示全排列已經生成
# 也就是符合情況的選擇已經選擇完畢
# 將這個全排列的情況添加到串列中
# 這里需要注意，pmt 在引數傳遞是參考傳遞，拷貝一份添加到結果中
if depth == length:
ans.append(pmt[:])
return
# 開始遍歷
for i in range(length):
# be_selected，表示原陣列中的元素的狀態，是否被選擇，是為 True，否為 False
if not be_selected[i]:
# 當元素被選擇時，改變狀態
be_selected[i] = True
# 將元素添加到 pmt 中，以構成后續
pmt.append(nums[i])
# 向下一層進行遍歷
_dfs(nums, depth + 1, pmt, be_selected, length, ans)
# 遍歷結束時，進行回溯，這個時候狀態要進行重置
# 如上面說的 `[1, 2, 3]` 到 `[1, 3, 2]` 中變化，要撤銷 3，再撤銷 2，重新選擇
# 狀態改變
be_selected[i] = False
# 撤銷
pmt.pop()
length = len(nums)
if length == 0:
return []
be_selected = [False] * length
ans = []
_dfs(nums, 0, [], be_selected, length, ans)
return ans
實作結果
以上就是使用深度優化搜索的思想，解決《46. 全排列》的問題的主要內容，主要需要注意的是狀態重置，
歡迎關注微信公眾號《書所集錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/153375.html
標籤：Python
下一篇：python常用內置函式使用