46. 全排列 題目來源： "https://leetcode cn.com/problems/permutations/" 題目 給定一個 沒有重覆 數字的序列，返回其所有可能的全排列。 示例: 解題思路 思路：深度優化搜索 先看題目，以所給數組 [1, 2, 3] 的全排列為例： 以 1 開始， ...
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. 全排列》的問題的主要內容，主要需要註意的是狀態重置。
歡迎關註微信公眾號《書所集錄》
