全排列問題是算法中的經典問題，其目標是將一組數字的所有可能排列組合列舉出來。本文將詳細解析如何通過深度優先搜索（DFS）和回溯法高效生成全排列，并通過模擬遞歸過程幫助讀者徹底掌握其核心思想。
問題描述
給定一個正整數?n，生成數字?1?到?n?的所有排列。例如，當?n = 3?時，輸出應為：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
算法思路
1. 核心變量
-
path[N]：存儲當前生成的排列。 -
dt[N]（bool?數組）：標記數字是否已被使用（避免重復）。 -
n：排列的長度（如?n=3?表示生成?1,2,3?的全排列）。
2. DFS遞歸函數
void dfs(int u) {if (u == n) { // 終止條件：排列已填滿print_permutation(); // 輸出當前排列return;}for (int i = 0; i < n; i++) {if (!dt[i]) { // 如果數字i未被使用path[u] = i; // 選擇idt[i] = true; // 標記為已使用dfs(u + 1); // 遞歸填充下一位dt[i] = false; // 回溯：恢復狀態}} }
3. 主函數
int main() {scanf("%d", &n);dfs(0); // 從第0位開始生成排列return 0; }
遞歸過程模擬（以n=2為例）
初始狀態
-
n = 2（排列長度為 2，數字為?1, 2，對應內部?0, 1）。 -
path = [?, ?]（未初始化）。 -
dt = [false, false]（初始均未使用）。
遞歸調用樹
第一層調用：dfs(0)
-
當前位?
u = 0（正在填充?path[0]）。 -
循環?
i = 0：-
dt[0]?為?false，選擇數字?0（實際輸出為?1）。 -
更新狀態：
-
path = [0, ?]。 -
dt = [true, false]。
-
-
遞歸進入?
dfs(1)。
-
第二層調用：dfs(1)
-
當前位?
u = 1（正在填充?path[1]）。 -
循環?
i = 0：-
dt[0]?為?true，跳過。
-
-
循環?
i = 1：-
dt[1]?為?false，選擇數字?1（實際輸出為?2）。 -
更新狀態：
-
path = [0, 1]。 -
dt = [true, true]。
-
-
遞歸進入?
dfs(2)。
-
第三層調用：dfs(2)
-
終止條件：
u == n（2 == 2），打印當前排列：-
輸出?
path[0]+1, path[1]+1?→?1 2。
-
-
返回上一級（回溯到?
dfs(1)）。
回溯到?dfs(1)
-
恢復狀態：
-
dt[1] = false（dt = [true, false]）。
-
-
循環結束，返回上一級?
dfs(0)。
回溯到?dfs(0)
-
恢復狀態：
-
dt[0] = false（dt = [false, false]）。
-
-
繼續循環?
i = 1：-
dt[1]?為?false，選擇數字?1（實際輸出為?2）。 -
更新狀態：
-
path = [1, ?]。 -
dt = [false, true]。
-
-
遞歸進入?
dfs(1)。
-
第二層調用：dfs(1)
-
當前位?
u = 1。 -
循環?
i = 0：-
dt[0]?為?false，選擇數字?0（實際輸出為?1）。 -
更新狀態：
-
path = [1, 0]。 -
dt = [true, true]。
-
-
遞歸進入?
dfs(2)。
-
第三層調用：dfs(2)
-
打印排列：
path[0]+1, path[1]+1?→?2 1。 -
返回上一級（回溯到?
dfs(1)）。
回溯到?dfs(1)
-
恢復?
dt[0] = false（dt = [false, true]）。 -
循環結束，返回?
dfs(0)。
回溯到?dfs(0)
-
恢復?
dt[1] = false（dt = [false, false]）。 -
循環結束，程序終止。
最終輸出
1 2 2 1
關鍵步驟總結
-
遞歸向下：逐層選擇未被使用的數字，更新?
path?和?dt。 -
回溯向上：在每一層遞歸返回時恢復?
dt?的狀態，確保其他分支能正確使用數字。 -
終止條件：當?
path?填滿時立即輸出結果。
遞歸樹圖示
dfs(0) │ ├─ i=0 (選1) │ ├─ dfs(1) │ │ ├─ i=1 (選2) → dfs(2) → 輸出 [1, 2] │ │ └─ 回溯：釋放2 │ └─ 回溯：釋放1 │ └─ i=1 (選2)├─ dfs(1)│ ├─ i=0 (選1) → dfs(2) → 輸出 [2, 1]│ └─ 回溯：釋放1└─ 回溯：釋放2
關鍵點總結
-
DFS的作用：遞歸地嘗試所有可能的數字選擇，直到填滿整個排列。
-
回溯的必要性：在遞歸返回時恢復?
dt?數組的狀態，確保后續分支能正確選擇數字。 -
時間復雜度：O(N×N!)，因為共有?
N!?種排列，每種排列需要 O(N) 時間生成。
優化與擴展
-
非遞歸實現：可以用棧模擬遞歸，避免遞歸深度過大（但對小規模?
n?影響不大）。 -
字典序排列：調整循環順序，使輸出按字典序排列。
-
去重排列：如果輸入包含重復數字，需額外判斷避免重復排列。
完整代碼（C語言）
? ? ? ?通過DFS和回溯的結合，我們可以高效地生成全排列。理解遞歸的展開與回溯是掌握該算法的關鍵。希望本文的逐步解析能幫助你徹底掌握這一經典問題！
