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