蓝桥杯试题：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;                   // 重置状态标记
                }
            }

        } 

核心逻辑

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原理的对应关系

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、算法特性分析

6、DFS的典型应用场景

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

2. 迷宫路径搜索

3. 树/图的遍历

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

5. 连通分量检测

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