什么是深度优先搜索（DFS）

DFS题型分类

DFS和回溯的关系

排列与组合

LeetCode 46 全排列

LeetCode 47 全排列 II

LeetCode 39 组合总和

LeetCode 40 组合总和 II

子集

LeetCode 78 子集

LeetCode 90 子集 II

分割问题

LeetCode 131 分割回文串

LeetCode 22 括号生成

图搜索类

LeetCode 79 单词搜索

LeetCode 200 岛屿数量

什么是深度优先搜索（DFS）

深度优先搜索（Depth-First Search，简称 DFS）是一种遍历或搜索图、树等数据结构的算法。其基本思想是尽可能深的搜索图的分支，当不能继续深度搜索时，回溯到上一个分支点，继续搜索其它未被访问过的路径。

DFS 的核心思想是通过递归或栈来实现对每个节点的深度遍历。

DFS的基本原理：
1. 起始点：从根节点（或图中的某个节点）开始
2. 访问节点：访问当前节点，并将其标记为已访问
3. 递归或栈操作：从当前节点的未访问邻接节点出发，递归地进行 DFS 搜索
4. 回溯：如果当前节点的所有邻接节点都已访问，则回溯到上一个节点，继续对其它未访问的节点进行 DFS 搜索

DFS的应用场景
图的遍历：DFS常用于在图中遍历所有节点和边，可以用于解决很多图算法问题，比如找连通分量、拓扑排序、环检测。
树的遍历：在树结构中，DFS通过先访问子节点再访问父节点，可以找到树的所有路径，比如路径和问题、最小/最大深度等。
回溯问题：DFS的一个重要应用是回溯问题，比如全排列、组合问题、数独问题，它通过递归的方式尝试所有可能的选择，直到找到符合条件的解。

DFS的实现方式
1. 递归实现：通过递归函数调用来模拟栈的行为。
2. 非递归实现：使用栈（或队列）显式地保存每一个待访问的节点。

递归实现
递归版 DFS 的流程简洁清晰，通过递归函数来实现深度优先的遍历。

void DFS(TreeNode* node) {if (node == nullptr) return;// 访问当前节点cout << node->val << " ";// 遍历左子树DFS(node->left);// 遍历右子树DFS(node->right);
}

非递归实现（栈版）
非递归版 DFS 使用栈显式地保存当前节点及其未访问的邻接节点。

void DFS(TreeNode* root) {stack<TreeNode*> s;if (root) s.push(root);while (!s.empty()) {TreeNode* node = s.top();s.pop();cout << node->val << " ";// 注意顺序：先右后左，因为栈是后进先出if (node->right) s.push(node->right);if (node->left) s.push(node->left);}
}

由于栈是后进先出，所以需要先把右子节点压入栈，才能确保左子节点在栈顶，优先被访问。

DFS的特点
空间复杂度：DFS 在递归实现中通常需要 O(h) 的栈空间，其中 h 为树的高度，最坏情况下是 O(n)，当树为链状结构时。
时间复杂度：对于图的 DFS，时间复杂度是 O(V + E)，其中 V 为节点数，E 为边数。对于树的 DFS，时间复杂度是 O(n)，其中 n 为节点数。

DFS题型分类

排列与组合类：
全排列：生成所有可能的排列
组合问题：从一个集合中选择多个元素（有时可以重复选择，有时不能）
常见题目：
LeetCode 46（全排列）
LeetCode 47（全排列 II）
LeetCode 39（组合总和）
LeetCode 40（组合总和 II）

子集类：
生成一个集合的所有子集，通常是二进制枚举的变种
常见题目：
LeetCode 78（子集）
LeetCode 90（子集 II）

分割问题：
将一个集合或数组划分成几个小部分或进行某种分割，通常需要满足特定条件
常见题目：
LeetCode 131（分割回文串）
LeetCode 22（括号生成）

图搜索类：
主要在二维网格或图结构中进行搜索，寻找特定的路径或模式
常见题目：
LeetCode 79（单词搜索）
LeetCode 200（岛屿数量）

数独与拼图类：
解决类似数独之类的填充或排列问题，使用回溯法逐步尝试填充，发现无解时撤回
常见题目：
LeetCode 37（数独解法）

DFS和回溯的关系

回溯法是一种算法思想，DFS 是实现回溯的常用手段。
DFS 的核心：是一种遍历或搜索策略，沿着一条路径尽可能深入地探索，直到无法继续再回溯到上一个节点，选择另一条路径继续探索。
回溯法的核心：是在搜索过程中，当发现当前路径不可能得到有效解时，主动放弃该路径（剪枝），回退到上一步重新选择，以避免无效搜索。
关系：
回溯法通常使用 DFS 来实现，但也可以用 BFS 等其他搜索方式
DFS 强调遍历的过程，回溯强调 "试错 - 回退 - 再试" 的决策过程
回溯法在 DFS 的基础上增加了剪枝操作，提高搜索效率

排列与组合

排列与组合问题是回溯算法中最基础的类型，它们通常涉及如何从一个集合中选择或排列元素

1. 排列问题：
排列指的是从一组元素中选取出所有可能的排列，排列中元素的顺序非常重要。
要求生成给定集合中所有元素的不同排列。
特点：
需要考虑元素的顺序，排列的结果与选取的元素顺序相关。
如果题目中有重复元素，需要进行去重处理，避免重复的排列。
排列问题可以通过递归（回溯）实现，逐步将元素放入不同的位置，尝试所有可能的排列。

LeetCode 46 全排列

解题思路：
回溯法核心思想：
每次选择一个元素：将数组中的每个元素都尝试放入不同的位置。
递归生成剩余的排列：当选定一个元素放入当前排列后，递归生成剩下的元素的排列。
回溯：当递归深入到最深层（即排列完成），就需要回溯到上一步，去尝试不同的元素组合。
去重：题目中已经保证了输入数组没有重复元素，所以不需要处理去重问题。

递归树的构建：
对于数组 [1, 2, 3]，第一层递归会选择 1、2、3 中的一个元素放入排列中。然后，递归地继续选择剩余的元素，直到数组中的元素都被选完为止。

vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;  // 存储所有排列结果vector<int> path;  // 存储当前路径（排列）dfs(nums, path, res);return res;  
}void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& res) {if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); ++i) {// 检查当前元素是否已在路径中if (find(path.begin(), path.end(), nums[i]) != path.end()) {continue;}path.push_back(nums[i]);  // 选择当前元素// 递归调用，继续构建路径dfs(nums, path, res);path.pop_back();  // 回溯，移除最后一个元素}
}

if (find(path.begin(), path.end(), nums[i]) != path.end())：

这个条件通过 find 函数检查 nums[i] 是否已经出现在当前排列 path 中

find 函数会返回一个迭代器，如果元素在 path 中找到了，返回的迭代器位置将不等于 path.end()。

如果 nums[i] 已经在 path 中，则跳过本次循环，继续检查下一个元素。这是为了避免重复的元素出现在排列中。

时间复杂度是 O(n!)，因为生成全排列需要遍历所有可能的排列，排列的总数为 n!
空间复杂度是 O(n)，因为递归的深度最多为 n，且每次递归都需要存储当前的排列。

LeetCode 47 全排列 II

vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> path;vector<bool> used(nums.size(), false);  // 标记元素是否被使用过sort(nums.begin(), nums.end());  // 排序使得相同元素相邻dfs(nums, used, path, res);return res;  
}void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); ++i) {if (used[i]) {continue;}// 去重关键：当前元素与前一个元素相同，且前一个元素未被使用时跳过if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {continue;}used[i] = true;path.push_back(nums[i]);dfs(nums, used, path, res);path.pop_back();used[i] = false;  }
}

sort(nums.begin(), nums.end()) 的作用是让相同的数字相邻，这样在回溯时才能用 nums[i] == nums[i-1] 判断重复并正确剪枝。如果不排序，相同的数字可能分散在数组各处，无法正确去重，从而生成重复的排列。
例如 nums = [1, 2, 1]：
当 i=2（nums[2] = 1），nums[i-1] = 2，nums[i] != nums[i-1]，所以不会跳过，导致重复选择 1

find(path.begin(), path.end(), nums[i]) 这种方法不能正确处理重复数字的排列问题
去重必须保证相同数字的使用顺序
如果 nums[i] == nums[i-1]，并且 nums[i-1] 还没被使用（!used[i-1]），说明 nums[i] 是重复的，应该跳过。这样才能保证相同数字按顺序被选中，避免重复排列。

find 无法实现这一点，find 只检查 nums[i] 是否在 current 中，但无法判断它是否是应该跳过的重复数字

第一层递归：
i=0：选 nums[0]=1 → 进入子树
i=1：发现 nums[1]=1 且 nums[0] 未被使用 → 跳过（剪枝）
i=2：选 nums[2]=2 → 进入子树

如果 nums[i] == nums[i-1] 且 !used[i-1]，说明 nums[i-1] 还没被选，但 nums[i] 却先被选了，这样会导致重复，所以跳过 nums[i]。
如果 used[i-1] == true，说明 nums[i-1] 已经被选了，nums[i] 可以正常选。

2. 组合问题：
组合指的是从一组元素中选取若干个元素，顺序不重要。
要求从给定集合中选取元素，不需要考虑顺序，输出所有的组合。
特点：
组合问题不关心顺序，只关心选取了哪些元素。
选取的元素数量可以固定，也可以可变。
如果有重复元素，通常需要进行去重处理。
组合问题的回溯通常是选择或不选择的决策过程，逐步选择元素并递归地生成组合。

LeetCode 39 组合总和

sort 函数把 candidates 数组从小到大排好。有两个好处：
方便剪枝：如果某枚硬币比剩下要凑的钱还多，后面更大的硬币肯定也凑不上，直接跳过
避免重复组合：通过控制只能从当前硬币及后面的硬币里选，避免[2,3] 和 [3,2] 这种重复情况
可以把这个题想象成凑硬币

dfs 参数介绍

参数名	含义	例子（目标 7，当前选了 2）
a	排序后的硬币数组（不能改）	[2,3,6,7]
start	从哪枚硬币开始选（控制不重复）	0（第一次选）、0（选了 2 后还能再选 2）
remain	还需要凑多少钱才能到目标	7（刚开始）、5（选了 2 后）
path	当前正在尝试的组合（能改，选硬币就加，不选就删）	[2]（刚选了第一个 2）
res	最终要返回的所有有效组合（能改，找到一个就加进去）	刚开始是空的，后来加 [2,2,3]

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); vector<vector<int>> res;vector<int> path;dfs(candidates, 0, target, path, res);return res;
}void dfs(const vector<int>& a, int start, int remain,vector<int>& path, vector<vector<int>>& res) {if (remain == 0) {               res.push_back(path);return;}for (int i = start; i < a.size(); ++i) {if (a[i] > remain) break;     // 剪枝path.push_back(a[i]);        dfs(a, i, remain - a[i], path, res); // 传 i 允许重复选path.pop_back();              // 撤销选择}
}

LeetCode 40 组合总和 II

代码和组合总和有两处不同：
1. dfs递归时传的是i + 1（而不是i），意思是下一次只能从当前元素的下一个开始选（避免重复使用同一个元素）
2. 多了一行if (i > start && a[i] == a[i - 1]) continue; 作用是去掉同一层循环中重复的元素（避免出现重复组合）为什么i > start？因为i == start时是第一个出现的元素，需要保留

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<vector<int>> res;vector<int> path;dfs(candidates, 0, target, path, res);return res;
}void dfs(const vector<int>& a, int start, int remain,vector<int>& path, vector<vector<int>>& res) {if (remain == 0) {res.push_back(path);return;}for (int i = start; i < a.size(); ++i) {if (a[i] > remain) break;                         // 剪枝if (i > start && a[i] == a[i - 1]) continue;      // 同层去重path.push_back(a[i]);dfs(a, i + 1, remain - a[i], path, res);          path.pop_back();}
}

子集

子集类题型的特点
1. 目标是生成所有子集（幂集）
给定一个数组，子集类问题的核心就是：对于每个元素，都有两种选择，即要或不要
所以总共有 2^n 种子集（包括空集和全集）

2. 顺序不重要
子集问题与排列不同，元素的顺序不影响子集的唯一性
例如 [1,2] 和 [2,1] 被认为是同一个子集
所以子集类问题的递归搜索常使用 start 参数，避免回头

3. 两种常见实现方式
回溯法（DFS）：递归过程中，把当前路径视为一个子集，依次探索「选择 / 不选择某个元素」的分支
二进制枚举：用一个二进制数表示某个元素是否被选入子集。例如 nums = [1,2,3]，101 表示子集 [1,3]

4. 是否包含重复元素 → 处理方式不同
无重复元素：直接回溯或枚举即可，典型题目是 LeetCode 78 子集
有重复元素：要做去重，和组合 II（LeetCode 40）的思路类似，需要排序+同层去重，典型题目是 LeetCode 90 子集 II

LeetCode 78 子集

方法一：DFS

vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;vector<int> path;dfs(nums, 0, path, res);return res;
}void dfs(const vector<int>& nums, int start,vector<int>& path, vector<vector<int>>& res) {res.push_back(path);for (int i = start; i < nums.size(); ++i) {path.push_back(nums[i]);          dfs(nums, i + 1, path, res);      path.pop_back();                   }
}

方法二：二进制枚举

vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size();vector<vector<int>> res;for (int mask = 0; mask < (1 << n); ++mask) {vector<int> path;for (int i = 0; i < n; ++i) {if (mask & (1 << i)) {path.push_back(nums[i]); // 该位为1则选}}res.push_back(move(path));}return res;
}

1 << n 是个位运算，意思是 1 向左移 n 位，等价于 2^n

mask & (1 << i) 可以判断 mask 的第 i 位是否为 1

move() 作用是将一个对象转换为右值引用
带 move 时：
path 中的数据直接被转移到 res 中，两者首元素地址相同（没有新内存分配）
转移后 path 变成空向量（资源已被取走）
不带 move 时：
res 中会生成新的拷贝，首元素地址和原 path 不同
path 仍然保留原有数据（内存未释放）

左值（Lvalue）：能放在赋值号左边的持久对象
本质：有明确的内存地址，且生命周期较长（比如函数内的局部变量、全局变量、数组元素等），可以被多次访问或修改。

右值（Rvalue）：只能放在赋值号右边的临时对象
本质：没有持久的内存身份，要么是临时生成的数值，要么是即将被销毁的对象，生命周期很短。

LeetCode 90 子集 II

vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());        // 排序便于同层去重vector<vector<int>> res;vector<int> path;dfs(nums, 0, path, res);return res;
}void dfs(const vector<int>& nums, int start,vector<int>& path, vector<vector<int>>& res) {res.push_back(path);for (int i = start; i < (int)nums.size(); ++i) {// 同层去重：本层已用过 nums[i-1] 作为起点，就不要再用相同值的 nums[i]if (i > start && nums[i] == nums[i - 1]) continue;path.push_back(nums[i]);dfs(nums, i + 1, path, res);     path.pop_back();}
}

同层去重：本层已用过 nums[i-1] 作为起点，就不要再用相同值的 nums[i]

分割问题

分割类问题的核心：在某些位置切或不切，形成搜索树
解法通常是回溯 + 剪枝，加上条件判断
难点在于：
如何快速判断切出来的部分是否合法（回文判定/括号合法等）
如何避免重复计算（可以用 DP 优化）

LeetCode 131 分割回文串

vector<vector<string>> partition(string s) {int n = s.size();vector<vector<string>> res;vector<string> path;// 预处理回文表vector<vector<bool>> isPal(n, vector<bool>(n, false));for (int i = n - 1; i >= 0; --i) {for (int j = i; j < n; ++j) {if (s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1])) {isPal[i][j] = true;}}}// 回溯切分dfs(s, 0, isPal, path, res);return res;
}void dfs(const string& s, int start,const vector<vector<bool>>& isPal,vector<string>& path,vector<vector<string>>& res) {if (start == s.size()) {     res.push_back(path);return;}for (int end = start; end < s.size(); ++end) {if (!isPal[start][end]) continue;           // 剪枝path.push_back(s.substr(start, end - start + 1));dfs(s, end + 1, isPal, path, res);        path.pop_back();                             }
}

dfs参数：
s：原始字符串
start：当前拆分的起始位置（从这里开始找下一个回文子串）
isPal：前面算好的回文表
path：当前正在拆分的方案
res：存储所有有效的拆分方案

以 s = "aab" 为例：

第一次调用 dfs：start=0（从开头开始拆），path 为空
循环 end 从 0 开始：
end=0：isPal[0][0]是 true（"a" 是回文）→ path 变成 ["a"] → 调用 dfs (start=1)
第二次调用 dfs：start=1（从索引 1 开始拆），path=["a"]
循环 end 从 1 开始：
end=1：isPal[1][1]是 true（"a" 是回文）→ path 变成 ["a","a"] → 调用 dfs (start=2)
第三次调用 dfs：start=2（从索引 2 开始拆），path=["a","a"]
循环 end=2：isPal[2][2]是 true（"b" 是回文）→ path 变成 ["a","a","b"] → 调用 dfs (start=3)
start=3 等于字符串长度 3 → 方案 ["a","a","b"] 加入 res
回溯后继续尝试：
回到 start=1 时，end=2：isPal[1][2]是 false（"ab" 不是回文）→ 跳过
回到 start=0 时，end=1：isPal[0][1]是 true（"aa" 是回文）→ path 变成 ["aa"] → 调用 dfs (start=2)
start=2 时选 "b" → path 变成 ["aa","b"] → 加入 res

最终 res 里就有了两种方案：[["a","a","b"], ["aa","b"]]

LeetCode 22 括号生成

思路：
只能在还没用完左括号时放 (：open < n
只能在当前序列仍然合法时放 )：close < open
终止：open == n && close == n，收集结果

vector<string> generateParenthesis(int n) {vector<string> res;string path;dfs(n, 0, 0, path, res);return res;
}void dfs(int n, int open, int close, string& path, vector<string>& res) {if (open == n && close == n) {   res.push_back(path);return;}if (open < n) {                  // 还能放左括号path.push_back('(');dfs(n, open + 1, close, path, res);path.pop_back();}if (close < open) {              // 右括号数量必须 < 左括号path.push_back(')');dfs(n, open, close + 1, path, res);path.pop_back();}
}

dfs参数：
n：需要生成的括号对数
open：当前已经用了多少个左括号 (
close：当前已经用了多少个右括号 )
path：当前正在构建的括号串
res：存储所有有效的括号组合

图搜索类

题目一般给一个二维矩阵（grid）、迷宫地图或者图（Graph），要求搜索是否存在路径、找出所有路径、或者计算最短路径。

常用搜索方式
DFS（深度优先搜索）
沿着一个方向不断深入，直到走不通再回溯
适合：判断连通性、找路径、求面积、遍历所有可能
BFS（广度优先搜索）
从起点出发，一层层向外扩展
适合：求最短路径（层数 = 步数）

常用技巧
访问标记（visited）：避免重复走已经访问过的点，防止无限循环
方向数组（dx, dy）：简化对上下左右的遍历

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

问题模式
是否存在路径：DFS 或 BFS，典型如单词搜索（79）
连通块计数：DFS/BFS 遍历整张图，典型如岛屿数量（200）
最短路径：BFS（层数就是最短步数），典型如最短路径 in 二维网格、迷宫问题
复杂约束：结合回溯，典型如数独求解（37）

复杂度特点
DFS/BFS 都是 O(V+E)（顶点+边），二维网格里一般是 O(m·n)
回溯题型则会指数爆炸，但剪枝能优化

LeetCode 79 单词搜索

方法一：使用 visited 数组

bool exist(vector<vector<char>>& board, string word) {int m = board.size(), n = board[0].size();vector<vector<int>> vis(m, vector<int>(n, 0));// 找可能的起点for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (board[i][j] == word[0] && dfs(board, word, i, j, 0, vis))return true;}}return false;
}const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};bool dfs(vector<vector<char>>& b, const string& w,int x, int y, int k, vector<vector<int>>& vis) {if (k == w.size()) return true;    // 终止条件int m = b.size(), n = b[0].size();// 剪枝if (x < 0 || x >= m || y < 0 || y >= n) return false;if (vis[x][y] || b[x][y] != w[k]) return false;vis[x][y] = 1;   // 标记// 向四个方向探索（下、上、右、左）for (int dir = 0; dir < 4; ++dir) {int nx = x + dx[dir], ny = y + dy[dir];if (dfs(b, w, nx, ny, k + 1, vis)) return true;}// 四个方向都走不通，进行回溯vis[x][y] = 0;                                        return false;
}

dfs参数：
b：网格
w：要找的单词
x,y：当前所在的网格坐标
k：当前要匹配的单词字符索引（比如 k=0 表示要匹配 word [0]）
vis：标记已使用单元格的数组

方法二：原地标记（省内存）

用一个特殊字符（#）暂存覆盖，以表示已访问，回溯时再还原

bool exist(vector<vector<char>>& board, string word) {int m = board.size(), n = board[0].size();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (dfs(board, word, i, j, 0)) return true;}}return false;
}const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};bool dfs(vector<vector<char>>& b, const string& w, int x, int y, int k) {if (k == w.size()) return true;int m = b.size(), n = b[0].size();if (x < 0 || x >= m || y < 0 || y >= n) return false;if (b[x][y] != w[k]) return false;char keep = b[x][y];b[x][y] = '#';                // 原地标记为已用for (int dir = 0; dir < 4; ++dir) {int nx = x + dx[dir], ny = y + dy[dir];if (dfs(b, w, nx, ny, k + 1)) {b[x][y] = keep;        // 回溯前还原return true;}}b[x][y] = keep;            // 还原return false;
}

LeetCode 200 岛屿数量

思路：发现一个岛，就清空一个岛
遍历整个网格，只要遇到一个没被访问过的陆地（'1'），就说明发现了一个新岛屿；
然后用 DFS 把这个岛屿上所有相连的陆地都 “变成水”（标记为 '0'），避免重复统计；
最后统计这样的 “新岛屿” 有多少个。

int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size();int ans = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {   // 发现新岛屿++ans;dfs(grid, i, j);     // 淹没岛屿}}}return ans;
}void dfs(vector<vector<char>>& g, int x, int y) {int m = g.size(), n = g[0].size();if (x < 0 || x >= m || y < 0 || y >= n || g[x][y] != '1') return;g[x][y] = '0'; // 标记为已访问const int dx[4] = {1, -1, 0, 0};const int dy[4] = {0, 0, 1, -1};for (int d = 0; d < 4; ++d) {dfs(g, x + dx[d], y + dy[d]);}
}