46. 全排列
一、算法邏輯（逐步通順講解每一步思路）
該算法使用了典型的 回溯（backtracking）+ 狀態數組 思路，逐層遞歸生成排列。
題目目標：給定一個無重復整數數組 nums，返回其所有可能的全排列。
具體思路如下：
? 1?? 初始化變量：
-
n = len(nums)：數組長度，表示排列長度； -
ans = []：最終結果列表，保存所有排列； -
path = [0] * n：當前正在構造的排列路徑（長度固定為 n）； -
on_path = [False] * n：記錄哪些下標的元素已經被使用，用來避免重復選擇。
? 2?? 定義遞歸函數 dfs(i)：表示當前正在構建第 i 位上的數字。
-
遞歸終止條件：當
i == n，說明整個排列已經構造完成，path中已有一個完整解；-
使用
path.copy()將當前路徑添加到ans中（防止引用修改）。
-
? 3?? 遍歷所有可選數字：
-
遍歷
nums中每個元素（通過索引j）； -
只有當
on_path[j] == False，才說明當前數字nums[j]還沒被選過； -
將
nums[j]放入第i位的path[i]中，并標記為已使用； -
然后遞歸下一層
dfs(i+1)； -
回溯回來后，將
on_path[j]設為False，撤銷選擇，進入下一個分支。
? 4?? 啟動遞歸：
從 dfs(0) 開始，構造第 0 位，依次遞歸直到第 n-1 位，生成所有可能排列。
二、核心點總結
該算法的核心是：
使用回溯（DFS）方式按位構建排列，每一層遞歸嘗試將所有未使用的數字填入當前位置，通過布爾數組標記狀態，避免重復選擇，實現全排列。
? 回溯模板典型寫法（構造 + 撤銷）；
? 使用顯式路徑數組 path[i] 來記錄當前位置數字；
? 使用布爾標記數組 on_path 控制元素是否被使用；
? 整體結構是“選擇—遞歸—撤銷選擇”的排列構造范式。
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)ans = []path = [0] * non_path = [False] * ndef dfs(i:int) -> None:if i == n:ans.append(path.copy())return for j, on in enumerate(on_path):if not on:path[i] = nums[j]on_path[j]=Truedfs(i+1)on_path[j] = Falsedfs(0)return ans三、時間復雜度分析
-
一共有
n!個不同的排列； -
每個排列的構造過程為 O(n)，因為每一層選擇都要掃描一遍
on_path。
所以總時間復雜度為：
O(n × n!)
四、空間復雜度分析
-
顯式開銷：
-
path數組：O(n) -
on_path數組：O(n)
-
-
隱式開銷（遞歸棧）：
-
最多遞歸
n層（深度為 n）
-
所以總空間復雜度為：
O(n)（不包含輸出）
如果包含所有輸出結果，則為：
O(n × n!)（因為結果中包含 n! 個長度為 n 的排列）
? 總結一句話
該算法采用典型回溯框架，按位構造路徑、記錄狀態、遞歸搜索，最終在 O(n × n!) 時間與 O(n) 空間下枚舉出所有排列，是解決排列問題最通用、穩定的模板方案。
)
