蓝桥杯试题：DFS回溯

一、题目要求

输入一个数组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~n for (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; // 重置状态标记 } } } 核心逻辑

主方法（main）：

创建标记数组v（索引1到n标记数字是否被使用）。

调用DFS函数生成排列。

遍历结果列表list，输出所有排列。

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） 是一种"先探到底再回溯"的算法，其核心特征是：

优先沿着一条路径深入探索到底

遇到终点或无法继续时回溯到最近的分支点

通过递归或栈结构实现路径记录和状态回退

基础语法：

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]=0 i=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的典型应用场景

全排列/组合问题（如本代码所示）

迷宫路径搜索

树/图的遍历

棋盘类游戏解法（八皇后、数独等）

连通分量检测

---

通过这种递归+回溯的实现方式，DFS算法能系统性地遍历所有可能的解空间，特别适合需要穷举所有可能性的场景。代码中通过标记数组和列表操作，清晰地展现了DFS的核心思想。