DFS算法篇：理解递归，熟悉递归，成为递归

创作时间:

作者:

@小白创作中心

DFS算法篇：理解递归，熟悉递归，成为递归

引用

CSDN

https://m.blog.csdn.net/2301_80260194/article/details/145686767

深度优先搜索（DFS）是一种重要的算法思想，在编程和算法竞赛中有着广泛的应用。本文从递归的基本概念出发，深入讲解DFS的原理，并通过多个具体题目来展示DFS的应用。

1.DFS原理

深度优先搜索（DFS）本质上就是一个带路径的递归。要理解DFS，首先要理解递归。递归的过程可以分为两个阶段：“递”和“归”。

所谓的“递”，就是在函数内部调用自身。每次调用函数时，系统会在栈上开辟一份空间（称为栈帧），用于存储函数体内的局部变量。这种套娃行为会不断深入，形成一个层次结构，这就是为什么称之为“深度”优先搜索。

而所谓的“归”，就是在函数调用达到终止条件时，开始回溯。从最底层的函数调用开始，逐层返回到上一级函数，最终回到最初的调用点。

在理解递归时，可以通过画图来梳理函数之间的调用关系。如果一个函数在内部多次调用自身，那么这种场景就形成了DFS的情况，可以用树状结构来描述。在执行递归函数时，这个过程类似于遍历一棵多叉树，通常是前序遍历（先遍历左子树再遍历右子树）。

在DFS中，除了记录路径信息外，还可以通过数组或表等结构记录遍历过程中的节点内容。而不带路径的递归，如斐波那契数列的计算，通常用于动态规划。

2.应用

题目一：字符串的全部子序列难度：EZ

题目：给定一个字符串a，求其全部子序列。

思路：通过枚举每个位置的字符是否存在于子序列中，可以构建一棵完全展开的二叉树。从根节点到叶子节点的每条路径代表一个子序列。

代码实现：

class Solution {
public:
    void dfs(string& a, vector<string>& ans, string temp, int i) {
        if (i == a.size()) {
            ans.push_back(temp);
            return;
        }
        dfs(a, ans, temp + a[i], i + 1); // 当前字符存在在子序列中
        dfs(a, ans, temp, i + 1); // 当前字符不存在在子序列中
    }
    void allSubstrings(string& a, vector<string>& ans) {
        string temp;
        dfs(a, ans, temp, 0);
    }
};

题目二：字符串的全部不重复的子序列难度：EZ

题目：给定一个字符串a，求其全部且不重复的子序列。

思路：在上一题的基础上，使用哈希表进行去重处理。

代码实现：

class Solution {
public:
    void dfs(string& a, vector<string>& ans, string temp, int i, unordered_map<string, int>& value) {
        if (i == a.size()) {
            if (value.find(temp) == value.end()) {
                ans.push_back(temp);
                value[temp]++;
            }
            return;
        }
        dfs(a, ans, temp + a[i], i + 1, value);
        dfs(a, ans, temp, i + 1, value);
    }
    void allSubstrings(string& a, vector<string>& ans) {
        string temp;
        unordered_map<string, int> value;
        dfs(a, ans, temp, 0, value);
    }
};

题目三：子集难度：MID

题目：给定一个数组，返回所有且不重复的子集。

思路：通过枚举每个位置的元素是否存在于子集中，构建决策树。可以进一步优化，通过排序和剪枝减少重复计算。

代码实现：

class Solution {
public:
    void dfs(const vector<int>& nums, vector<vector<int>>& subsets, vector<int>& current, int index) {
        if (index == nums.size()) {
            subsets.push_back(current);
            return;
        }
        int i = index + 1;
        while (i < nums.size() && nums[i] == nums[i - 1]) {
            i++;
        }
        for (int j = 0; j < i - index; j++) {
            current.push_back(nums[index]);
            dfs(nums, subsets, current, i);
        }
        for (int j = 0; j < i - index; j++) {
            current.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        sort(nums.begin(), nums.end());
        dfs(nums, result, current, 0);
        return result;
    }
};

题目四：全排列难度：MID

题目：给定一个数组，求其所有全排列。

思路：通过枚举每个位置的元素，构建多叉树。使用一个检查数组来避免重复元素的选取。

代码实现：

class Solution {
public:
    void dfs(vector<int>& a, vector<vector<int>>& ans, vector<int>& temp, vector<int>& check) {
        if (temp.size() == a.size()) {
            ans.push_back(temp);
            return;
        }
        for (int i = 0; i < a.size(); i++) {
            if (check[i] == 0) {
                check[i] = 1;
                temp.push_back(a[i]);
                dfs(a, ans, temp, check);
                check[i] = 0;
                temp.pop_back();
            }
        }
    }
    void all(vector<int>& a, vector<vector<int>>& ans) {
        vector<int> temp;
        vector<int> check(a.size(), 0);
        dfs(a, ans, temp, check);
    }
};