Permutations排列
用 used 陣列或交換法。
用在：排程順序、路徑列舉
01為什麼需要它
一台機器要處理 6 個訂單，每個訂單之間切換模具的時間不同，順序不同總耗時就不同。要找最省時的順序。
為什麼用它順序問題和子集問題不同：同一批東西換個順序就是不同答案。6 個訂單有 6! = 720 種順序，全部列出來各算一次總耗時就好。這是排程問題在 n 小時最直接的解法，也是理解 TSP 這類問題的起點。
外送員從店家出發要送 5 個地點再回來，哪個順序總距離最短？
為什麼用它5 個地點的所有拜訪順序就是 5 的全排列。用 used 陣列記住哪些地點已經排進路線，每一步從還沒排的裡面挑，走到底就是一條完整路線。
把「listen」的字母重新排列能拼出哪些字？測試帳號的密碼是幾個片段的某種順序，要把所有順序都試一遍。
為什麼用它字母的重新排列就是排列。有重複字母時要避免產生一樣的結果，排序後加一條「相同的值前一個沒用就跳過」的規則即可。
看到這些關鍵字就想到它：順序、排法、有幾種排法、每個元素恰好用一次、n!、字母重組、路線的拜訪順序。
02核心概念
子集是對每個元素問「選不選」，排列則是對每個位置問「放誰」。第一個位置有 n 個選擇，第二個位置剩 n−1 個，依此類推，葉節點共 n! 個。決策樹不再是二元的，每層的分支數等於「還沒用過的元素數」。
要知道誰還沒用過，最直接的做法是一個 used 陣列。每層 for 迴圈掃過所有元素，used[j] 為 true 就跳過，否則做選擇（標記 used、放進 path）、遞迴到下一個位置、撤銷選擇（拿掉、取消標記）。撤銷必須把兩樣東西都復原，少一個下個分支就會看到錯誤的狀態，這是排列最常見的 bug。
交換法省掉 used 和 path：位置 i 依序和 i 之後的每個元素交換，前 i 個就是已經決定的部分、後面就是還沒用的部分。遞迴回來時再換回去。它少一個陣列，但產生的順序和 used 版不同，遇到重複元素也比較難處理。
複雜度是 O(n!·n)：n! 個排列各複製 O(n)。n = 10 是三百六十萬，n = 12 已經四億多，所以排列只能在 n 很小時完整列舉；n 大時題目通常要的是「最佳的一種」，那就得轉向 DP（例如狀態壓縮）或貪婪。重複元素的處理是先排序，同一層裡若 nums[j] == nums[j-1] 且 used[j-1] 為 false，表示這個值在同一層已經當過開頭，跳過。
03演算法步驟
- 1準備
ans、path與used（全 false）。dfs()表示「決定下一個位置放誰」。 - 2終止條件：
len(path) == n，所有位置都填了，複製path放進ans。 - 3for 迴圈掃過每個 j：
used[j]為 true 就 continue。 - 4做選擇：
used[j] = True、path.append(nums[j])，遞迴dfs()。 - 5撤銷選擇：
path.pop()、used[j] = False，兩樣都要復原，然後試下一個 j。
04互動示範
[1, 2, 3] 的排列樹。每一層從 used 為 false 的數字裡挑，下方同時顯示 used 陣列和路徑。留意每次撤銷時 used 和路徑是一起復原的。
05程式碼
used 陣列版、交換法，以及含重複元素的版本。三者的骨架都是「做選擇、遞迴、撤銷」，差在怎麼記錄「誰還沒用」。
# 全排列（LeetCode 46）：used 陣列記錄誰已經在路徑上
def permute(nums):
ans = []
path = []
used = [False] * len(nums)
def dfs():
if len(path) == len(nums): # 每個位置都填了
ans.append(path[:])
return
for j in range(len(nums)):
if used[j]: # 已經在路徑上，跳過
continue
used[j] = True # 做選擇
path.append(nums[j])
dfs()
path.pop() # 撤銷選擇
used[j] = False
dfs()
return ans
# 交換法：第 i 個位置和 i 之後的每個元素交換，不用 used 也不用 path
def permute_swap(nums):
ans = []
def dfs(i):
if i == len(nums):
ans.append(nums[:])
return
for j in range(i, len(nums)):
nums[i], nums[j] = nums[j], nums[i] # 做選擇：nums[j] 放到位置 i
dfs(i + 1)
nums[i], nums[j] = nums[j], nums[i] # 撤銷：換回來
dfs(0)
return ans
# 含重複元素的排列（LeetCode 47）：排序後，相同的值必須「前一個用了才能用後一個」
def permute_unique(nums):
nums = sorted(nums) # 排序出新串列，不改動呼叫者的輸入
ans = []
path = []
used = [False] * len(nums)
def dfs():
if len(path) == len(nums):
ans.append(path[:])
return
for j in range(len(nums)):
if used[j]:
continue
if j > 0 and nums[j] == nums[j - 1] and not used[j - 1]:
continue # 同樣的值已經在這個位置試過
used[j] = True
path.append(nums[j])
dfs()
path.pop()
used[j] = False
dfs()
return ans
if __name__ == "__main__":
print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(permute_swap([1, 2, 3])) # 同樣 6 個，但最後兩個順序不同
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
print(permute_unique([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]06練習題
- LeetCode 46PermutationsMedium
- LeetCode 47Permutations II（排序加 used[j-1] 判斷）Medium
- LeetCode 31Next Permutation（不用回溯，找下一個字典序）Medium
- LeetCode 526Beautiful ArrangementMedium
- LeetCode 60Permutation Sequence（用階乘直接算第 k 個）Hard
- LeetCode 996Number of Squareful ArraysHard