一、題目要求

輸入一個數組n，輸出1到n的全排列

二、代碼展示

import java.util.*;public class ikun {static List<List<Integer>> list = new ArrayList<>();public static void main(String[] args) {    Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] v = new int[n + 1];List<Integer> res = new ArrayList<>();dfs(n,v,res);for (List<Integer> x:list){for (int y:x){System.out.print(y + " ");}System.out.println();}}public static void dfs(int n, int[] v, List<Integer> res) {// 終止條件：當當前排列長度等于n時if (res.size() == n) {// 深拷貝當前排列結果到結果集list.add(new ArrayList<>(res));return; // 結束當前遞歸分支}// 遍歷所有數字1~nfor (int i = 1; i <= n; i++) {// 跳過已使用的數字（剪枝操作）if (v[i] == 1) continue;// 選擇階段：將數字i加入當前排列res.add(i);           // 操作路徑v[i] = 1;             // 更新狀態標記// 遞歸深入：探索下一層決策樹dfs(n, v, res);       // 進入新的遞歸層級// 回溯階段：撤銷當前選擇res.remove(res.size() - 1); // 移除最后一個元素（i）v[i] = 0;                   // 重置狀態標記}}} 

核心邏輯

1. 主方法（main）：

   • 創建標記數組v（索引1到n標記數字是否被使用）。

   • 調用DFS函數生成排列。

   • 遍歷結果列表list，輸出所有排列。

2. DFS方法（dfs）：

   • 終止條件：當臨時結果res的大小等于n時，將當前排列存入list。

   • 遞歸過程：

     • 遍歷數字1到n。

     • 若當前數字未被使用（v[i] == 0）：

       • 將數字加入res，并標記為已使用。

       • 遞歸調用DFS，繼續生成剩余位置的排列。

       • 回溯：遞歸返回后，移除res末尾元素，并重置標記，以便嘗試其他數字。

關鍵點分析

• 標記數組v：用于避免重復使用數字。v[i] = 1表示數字i已被使用。

• 回溯機制：在遞歸返回后，撤銷當前選擇（移除res末尾元素，重置標記），確保后續分支的正確性。

• 結果存儲：每次找到完整排列時，復制res到list（避免后續修改影響已存結果）。

三、DFS算法

1、DFS算法核心思想

深度優先搜索（DFS）?是一種"先探到底再回溯"的算法，其核心特征是：

1. 優先沿著一條路徑深入探索到底

2. 遇到終點或無法繼續時回溯到最近的分支點

3. 通過遞歸或棧結構實現路徑記錄和狀態回退

基礎語法：

public static void dfs(){if (當前狀態 == 目標狀態){//邏輯處理return;}for (尋找新狀態){if (狀態合法){dfs(新狀態);}}}

回溯

 public static void dfs(){if (當前狀態 == 目標狀態){//邏輯處理return;}for (查找新狀態){if (狀態合法){//標記當前狀態已訪問dfs(新狀態);//撤銷標記}}}

---

2、代碼中的DFS實現解析

代碼結構概覽

static List<List<Integer>> list = new ArrayList<>(); // 存儲所有排列結果public static void dfs(int n, int[] v, List<Integer> res) {// 終止條件if (res.size() == n) {list.add(new ArrayList<>(res)); // 保存當前排列return;}// 遍歷所有可能選擇for (int i = 1; i <= n; i++) {if (v[i] == 1) continue;  // 跳過已使用的數字// 做選擇res.add(i);v[i] = 1;// 遞歸深入dfs(n, v, res);// 撤銷選擇（回溯）res.remove(res.size() - 1);v[i] = 0;}
}

3、代碼與DFS原理的對應關系

DFS階段	代碼實現	說明
1. 路徑選擇	res.add(i)	將當前數字加入排列路徑
2. 狀態標記	v[i] = 1	標記該數字已被使用
3. 遞歸深入	dfs(n, v, res)	進入下一層決策樹
4. 回溯恢復	res.remove(...); v[i] = 0	返回上層時撤銷選擇
5. 終止條件	if (res.size() == n)	當路徑長度等于n時記錄結果

---

4、執行流程演示（n=2）

初始調用：dfs(2, [0,0,0], [])↓
i=1被選中：res=[1], v=[0,1,0]→ 遞歸調用 dfs(2, [0,1,0], [1])↓i=2被選中：res=[1,2], v=[0,1,1]→ 記錄結果 [1,2]← 回溯：res變為[1], v[2]=0← 返回上層← 回溯：res變為[], v[1]=0i=2被選中：res=[2], v=[0,0,1]→ 遞歸調用 dfs(2, [0,0,1], [2])↓i=1被選中：res=[2,1], v=[0,1,1]→ 記錄結果 [2,1]← 回溯：res變為[2], v[1]=0← 返回上層← 回溯：res變為[], v[2]=0

---

5、算法特性分析

特性	本代碼中的體現
時間復雜度	O(n!) - 需要生成n!種排列
空間復雜度	O(n) - 遞歸棧深度為n
回溯機制	通過remove和v[i]=0顯式實現狀態回退
剪枝優化	使用v數組避免重復選擇
結果存儲	使用new ArrayList<>(res)深度拷貝當前狀態

---

6、DFS的典型應用場景

1. 全排列/組合問題（如本代碼所示）

2. 迷宮路徑搜索

3. 樹/圖的遍歷

4. 棋盤類游戲解法（八皇后、數獨等）

5. 連通分量檢測

---

通過這種遞歸+回溯的實現方式，DFS算法能系統性地遍歷所有可能的解空間，特別適合需要窮舉所有可能性的場景。代碼中通過標記數組和列表操作，清晰地展現了DFS的核心思想。