DFS是什么
DFS是深度优先搜索，具体做法是从一个起始节点开始，尽可能深入地搜索每个分支，直到到达叶子节点或没有更多的未访问节点为止，然后回溯到最近的分支点，继续探索其他未访问的节点
DFS的基本思想
- 起始节点：从一个起始节点开始
- 访问节点：访问当前节点并标记为访问
- 递归或栈：对每个未访问的邻接节点，递归地进行DFS或使用栈来模拟递归过程
- 回溯：当没有更多未访问的邻接节点时，回溯到上一个节点，继续探索其他路径
- 结束条件：直到所有节点都被访问过，或者找到目标为止
DFS的特点
- 空间复杂度取决于树的深度，在最坏的情况下（例如数的深度为n），空间复杂度为O(n)
- 时间复杂度为O(V+E），V是图中顶点数量，E是图中的边数量
- 适用于无向图和有向图
DFS可以解决的问题
- 路径查找：在图中查找从一个节点到另一个节点的路径
- 连通性检测：检查图中是否存在路径连接两个节点
- 拓扑排序：在有向无环图中，DFS可以用于生成拓扑排序
- 寻找强连通分量：在有向图中，DFS可以用于找到所有强连通分量（即每个节点都可以到达其他节点的子图）
- 迷宫问题：在迷宫中找到从起点到终点的路径
- 生成组合和排列：DFS可以用于生成所有可能的组合或排列
- 图的遍历：DFS本身就是一种图的遍历方法，可以访问所有节点
- 求解棋类游戏：在棋类游戏（如国际象棋）中，DFS可以用于模拟所有可能的棋局
利用DFS记录路径
思路首先定义存储的数据结构：vector<int> path 和vector<vector<int>> ans; path用于存储满足条件的一条路径，ans记录满足条件的所有pathdfs的思路：判断是否满足，对于左右端点是否为空进入下一个dfs，最后进行回溯
给定一个不重复数字的数组nums，找出所有的排列组合问题可以提炼为从不重复数字的数组的每一个点为起点开始，搜索下一个不一样的点，直到所有点使用完成符合DFS的特征：寻找起点，递归终止条件所以需要定义一个存储节点的数组，一个存放最终结果的数组另外还需要设置递归终止条件为存储的数组的大小等于nums就return
在一个元素互不相同的数组中，提取所有可能的子集全组合就是对于数组的所有元素来说，以该元素为开头能有多少组合，从而可以思考为以数组的每一个元素为起始节点，以该节点之后的元素为路径选择（防止出现重复），直到最后一个元素
std::vector<std::string> mapping = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” };需要定义一个字符串集合，需要有模拟的思想，其他的与DFS类似，从第一个里面选一个作为起始节点，再选其他的，直到大小相等
对于一个无重复元素的整数数组，和一个目标值target，可以从该整数数组选出一个可以重复数字的组合问题可以视为对于数组的每一个元素，以每个元素为开头，选择自身以及后面的元素作为自身的组合（选择自身是为了元素可重复），直到某个组合值与目标值相同，最后到达最后一个元素
分割字符串是将字符串s分割成一些回文串问题可以视为对于字符串s的开始找，也就是记录下标start和end来判断是否是回文串，直到start为s.size