Problem: 46. 全排列
文章目錄
- 整體思路
- 完整代碼
- 時空復雜度
- 時間復雜度：O(N * N!)
- 空間復雜度：O(N)
整體思路
這段代碼旨在解決一個經典的組合數學問題：全排列 (Permutations)。給定一個不含重復數字的數組 nums，它需要找出其所有可能的全排列，并返回一個包含這些排列的列表。
該算法采用的核心方法是 回溯法（Backtracking），這是一種通過 深度優先搜索（DFS） 來系統地探索所有可能解的搜索策略。
算法的整體思路可以分解為以下步驟：
-
逐位構建排列：
- 算法將生成一個排列的過程看作是逐個“填空”的過程。它定義了一個
dfs(i, ...)函數，其核心任務是確定排列中第i個位置應該填入哪個數字。
- 算法將生成一個排列的過程看作是逐個“填空”的過程。它定義了一個
-
狀態維護：
- 為了輔助構建過程，算法使用了兩個關鍵的數據結構：
List<Integer> path：用于存儲當前正在構建的排列。boolean[] onPath：一個與原數組nums等長的布爾數組，用作“訪問標記”。onPath[j] = true表示nums[j]這個數字已經被放入了當前的path中，不能再被使用。
- 為了輔助構建過程，算法使用了兩個關鍵的數據結構：
-
遞歸與回溯的核心邏輯：
dfs函數從第 0 位開始 (i=0)。在為第i位選擇數字時，它會遍歷整個原始數組nums。- 對于
nums中的每一個數字nums[j]，它會檢查該數字是否已被使用（if (!onPath[j])）。 - 選擇 (Choose)：如果
nums[j]未被使用，就做出選擇：
a. 將nums[j]放入當前排列的第i位：path.set(i, nums[j])。
b. 將nums[j]標記為已使用：onPath[j] = true。 - 探索 (Explore)：做出選擇后，遞歸地調用
dfs(i + 1, ...)，去解決下一個子問題——填充第i+1位。 - 撤銷選擇 (Unchoose / Backtrack)：當對
i+1位的探索（即dfs(i + 1, ...)調用）返回后，必須撤銷剛才的選擇。這是回溯法的精髓。
a. 將nums[j]標記為未使用：onPath[j] = false。
b. 這樣，在下一次循環中，nums[j]就可以被用來填充其他位置，從而形成不同的排列。
-
遞歸終止條件：
- 當
i的值等于數組長度n時（if (i == n)），意味著排列的所有n個位置都已經被成功填滿。 - 此時，一個完整的排列就構建好了（存儲在
path中）。 - 將
path的一個深拷貝（new ArrayList<>(path)）添加到最終的結果列表ans中。必須使用拷貝，因為path本身會在回溯過程中被不斷修改。
- 當
通過這個“選擇-探索-撤銷”的循環，算法能夠不重不漏地遍歷所有可能的排列組合。
完整代碼
class Solution {/*** 計算給定數組的全排列。* @param nums 不含重復數字的整數數組* @return 包含所有全排列的列表*/public List<List<Integer>> permute(int[] nums) {int n = nums.length;// ans: 最終的結果列表List<List<Integer>> ans = new ArrayList<>();// path: 用于存儲當前正在構建的單個排列路徑// Arrays.asList(new Integer[n]) 創建一個固定大小的、由null填充的List，便于后續使用 set 方法List<Integer> path = Arrays.asList(new Integer[n]);// onPath: 標記數組，onPath[j]為true表示nums[j]已在當前path中boolean[] onPath = new boolean[n];// 從第 0 個位置開始進行深度優先搜索dfs(0, nums, ans, path, onPath);return ans;}/*** 深度優先搜索（回溯）輔助函數。* @param i 當前需要填充的排列位置的索引* @param nums 原始輸入數組* @param ans 結果列表* @param path 當前構建的排列* @param onPath 標記數組*/private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] onPath) {int n = nums.length;// 遞歸終止條件：當 i 等于 n 時，說明所有位置都已填滿，一個完整的排列已生成if (i == n) {// 將當前路徑的一個深拷貝加入到結果列表中// 必須是深拷貝，因為 path 會在回溯過程中被修改ans.add(new ArrayList<>(path));return; // 結束當前遞歸分支}// 遍歷所有可用的數字，嘗試將其放入第 i 個位置for (int j = 0; j < n; j++) {// 如果 nums[j] 還未在當前路徑中使用過if (!onPath[j]) {// 選擇：將 nums[j] 放入第 i 個位置path.set(i, nums[j]);// 標記 nums[j] 為已使用onPath[j] = true;// 探索：遞歸地去填充下一個位置 (i + 1)dfs(i + 1, nums, ans, path, onPath);// 撤銷選擇（回溯）：將 nums[j] 標記為未使用，// 這樣它就可以在其他分支中被用于其他位置。這是回溯法的核心。onPath[j] = false;}}}
}
時空復雜度
時間復雜度：O(N * N!)
- 排列數量：對于一個包含
N個不同元素的集合，其全排列的數量是N!(N的階乘)。 - 構建每個排列的成本：
- 算法的搜索過程可以看作是在一棵“排列樹”上進行DFS。這棵樹有
N!個葉子節點，每個葉子節點代表一個完整的排列。 - 從根節點到任意一個葉子節點的路徑長度為
N。 - 當到達一個葉子節點時（即
i == n），需要執行new ArrayList<>(path)操作，這是一個 O(N) 的操作，用于復制當前排列。
- 算法的搜索過程可以看作是在一棵“排列樹”上進行DFS。這棵樹有
- 綜合分析：
- 總的時間復雜度約等于 (葉子節點數量 * 到達葉子節點的成本) + (非葉子節點的計算成本)。
- 非葉子節點的總數也與
N!相關。 - 一個更精確的視角是，總共有
N!個排列，每個排列的生成和復制都需要 O(N) 的時間。因此，總時間復雜度為 O(N * N!)。
空間復雜度：O(N)
- 主要存儲開銷：我們分析的是額外輔助空間，不包括存儲最終結果的
ans列表（否則空間將是 O(N * N!)）。List<Integer> path: 用于存儲當前路徑，其大小為N。空間復雜度為 O(N)。boolean[] onPath: 標記數組，其大小為N。空間復雜度為 O(N)。- 遞歸調用棧：
dfs函數的最大遞歸深度為N（從i=0到i=n）。因此，遞歸棧所占用的空間為 O(N)。
綜合分析：
算法所需的額外輔助空間由 path、onPath 和遞歸棧深度共同決定。它們都是 O(N) 級別的。因此，總的輔助空間復雜度為 O(N)。
參考靈神
)
