蓝桥杯试题：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~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的核心思想。