一、 問題描述給定一個不含重復數(shù)字的數(shù)組nums返回其所有可能的全排列。你可以按任意順序返回答案。示例輸入nums [1,2,3]輸出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]二、 核心思路回溯 (Backtracking)全排列問題是回溯算法最經(jīng)典的入門題。回溯算法的本質是決策樹的深度優(yōu)先遍歷 (DFS)。我們可以將全排列問題具象化為有n個空位我們需要從左到右依次填入nums中的數(shù)字。每個數(shù)字只能用一次。1. 狀態(tài)定義在遍歷決策樹的過程中我們需要維護以下幾個關鍵狀態(tài)路徑 (Path)記錄當前已經(jīng)做出的選擇即當前正在生成的排列。選擇列表當前還可以做出的選擇即數(shù)組中還未被使用的數(shù)字。結束條件到達決策樹底層無法再做選擇的條件。2. 關鍵難點如何記錄“已使用”由于數(shù)組中的元素不能重復使用我們需要一個標記機制。最直接的方法是引入一個布爾數(shù)組usedused[i] true表示nums[i]已經(jīng)在當前路徑中被使用。used[i] false表示nums[i]尚未被使用可以加入當前路徑。3. 回溯過程圖解以nums [1, 2, 3]為例決策樹的遍歷過程如下第一層可以選擇 1, 2, 3。第二層如果第一層選了 1第二層只能從 2, 3 中選。第三層如果前兩層選了 1, 2第三層只能選 3。當路徑長度達到 3 時記錄當前路徑并撤銷上一步選擇回溯返回上一層嘗試其他分支。三、 代碼實現(xiàn) (C)基于上述思路我們可以寫出非常標準的回溯代碼模板class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint result; vectorint path; vectorbool used(nums.size(), false); backtrack(nums, used, path, result); return result; } private: void backtrack(const vectorint nums, vectorbool used, vectorint path, vectorvectorint result) { // 1. 終止條件路徑長度等于數(shù)組長度說明找到了一個全排列 if (path.size() nums.size()) { result.push_back(path); return; } // 2. 遍歷選擇列表 for (int i 0; i nums.size(); i) { // 排除不合法的選擇當前數(shù)字已被使用 if (used[i]) continue; // 3. 做選擇 used[i] true; path.push_back(nums[i]); // 4. 進入下一層決策樹 backtrack(nums, used, path, result); // 5. 撤銷選擇 (回溯核心) path.pop_back(); used[i] false; } } };四、 復雜度分析時間復雜度O(n×n!)總共有 n! 種全排列。每種排列需要 O(n) 的時間將其從path復制到result中。遞歸樹的節(jié)點總數(shù)約為 e×n!因此整體時間復雜度為 O(n×n!)?？臻g復雜度O(n)遞歸調用棧的深度最大為 n。used數(shù)組和path數(shù)組的空間開銷均為 O(n)。注意返回結果result占用的空間不計入算法的輔助空間復雜度。五、 拓展與普適化回溯算法通用模板全排列問題揭示了回溯算法解決“組合/排列/子集”類問題的通用范式。我們可以將其抽象為以下偽代碼模板result [] def backtrack(路徑, 選擇列表): if 滿足結束條件: result.add(路徑) return for 選擇 in 選擇列表: 做選擇 backtrack(路徑, 新的選擇列表) 撤銷選擇