回溯算法题
目录
题目三—— 1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
题目四——47. 全排列 II - 力扣（LeetCode）
题目五——17. 电话号码的字母组合 - 力扣（LeetCode）
题目十——784. 字母大小写全排列 - 力扣（LeetCode）
题目十一—— 526. 优美的排列 - 力扣（LeetCode）
题目十三——36. 有效的数独 - 力扣（LeetCode）
题目十六——1219. 黄金矿工 - 力扣（LeetCode）
题目十七——980. 不同路径 III - 力扣（LeetCode）
前言
1.深度优先遍历和深度优先搜索（DFS)
- 深度优先遍历
主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。树是图的一种特例(连通无环的图就是树)，接下来我们来看看树用深度优先遍历该怎么遍历。
1、我们从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9。
2、上图中一条路已经走到底了(9是叶子节点，再无可遍历的节点)，此时就从 9 回退到上一个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进行深度优先遍历，如下：
3、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点，再往上回溯，发现 3 有除 6 以外的子点 7，所以此时会遍历 7。
3、从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进行遍历,这样就遍历完成了。
完整的节点的遍历顺序如下(节点上的的蓝色数字代表)：
相信大家看到以上的遍历不难发现这就是树的前序遍历,实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。
事实上，深度优先搜索和深度优先遍历本质是同一个东西，只不过
- 遍历是形式，目的是搜索
2.暴搜
其实搜索就是暴力枚举的一种方式。所以也叫暴搜
暴搜分为两种情况：DFS和BFS。
3.回溯
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。
回溯算法通常采用“深度优先搜索”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。
例如：
- 例题一
给定一棵二叉树，搜索并记录所有值为 7 的节点，请返回节点列表。
对于此题，我们前序遍历这棵树，并判断当前节点的值是否为 7 ，若是，则将该节点的值加入结果列表 res 之中。
/* 前序遍历：例题一 */
void preOrder(TreeNode *root) {
if (root == nullptr) {
return;
}
if (root->val == 7) {
// 记录解
res.push_back(root);
}
preOrder(root->left);
preOrder(root->right);
}
之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。
对于例题一，访问每个节点都代表一次“尝试”，而越过叶节点或返回父节点的 return 则表示“回退”。
值得说明的是，回退并不仅仅包括函数返回。为解释这一点，我们对例题一稍作拓展。
- 例题二
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径。
在例题一代码的基础上，我们需要借助一个列表 path 记录访问过的节点路径。当访问到值为 7 的节点时，则复制 path 并添加进结果列表 res 。遍历完成后，res 中保存的就是所有的解。代码如下所示：
/* 前序遍历：例题二 */
void preOrder(TreeNode *root) {
if (root == nullptr) {
return;
}
// 尝试
path.push_back(root);
if (root->val == 7) {
// 记录解
res.push_back(path);
}
preOrder(root->left);
preOrder(root->right);
// 回退
path.pop_back();
}在每次“尝试”中，我们通过将当前节点添加进 path 来记录路径；而在“回退”前，我们需要将该节点从 path 中弹出，以恢复本次尝试之前的状态。
观察下图所示的过程，我们可以将尝试和回退理解为“前进”与“撤销”，两个操作互为逆向。
4.剪枝
复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。
- 例题三
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 3 的节点。
为了满足以上约束条件，我们需要添加剪枝操作：在搜索过程中，若遇到值为 3 的节点，则提前返回，不再继续搜索。代码如下所示：
/* 前序遍历：例题三 */
void preOrder(TreeNode *root) {
// 剪枝
if (root == nullptr || root->val == 3) {
return;
}
// 尝试
path.push_back(root);
if (root->val == 7) {
// 记录解
res.push_back(path);
}
preOrder(root->left);
preOrder(root->right);
// 回退
path.pop_back();
}“剪枝”是一个非常形象的名词。如图所示，在搜索过程中，我们“剪掉”了不满足约束条件的搜索分支，避免许多无意义的尝试，从而提高了搜索效率。
5.框架代码
接下来，我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来，提升代码的通用性。
在以下框架代码中，state 表示问题的当前状态，choices 表示当前状态下可以做出的选择：
/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
// 判断是否为解
if (isSolution(state)) {
// 记录解
recordSolution(state, res);
// 不再继续搜索
return;
}
// 遍历所有选择
for (Choice choice : choices) {
// 剪枝：判断选择是否合法
if (isValid(state, choice)) {
// 尝试：做出选择，更新状态
makeChoice(state, choice);
backtrack(state, choices, res);
// 回退：撤销选择，恢复到之前的状态
undoChoice(state, choice);
}
}
} 接下来，我们基于框架代码来解决例题三。状态 state 为节点遍历路径，选择 choices 为当前节点的左子节点和右子节点，结果 res 是路径列表：
/* 判断当前状态是否为解 */
bool isSolution(vector<TreeNode *> &state) {
return !state.empty() && state.back()->val == 7;
}
/* 记录解 */
void recordSolution(vector<TreeNode *> &state, vector<vector<TreeNode *>> &res) {
res.push_back(state);
}
/* 判断在当前状态下，该选择是否合法 */
bool isValid(vector<TreeNode *> &state, TreeNode *choice) {
return choice != nullptr && choice->val != 3;
}
/* 更新状态 */
void makeChoice(vector<TreeNode *> &state, TreeNode *choice) {
state.push_back(choice);
}
/* 恢复状态 */
void undoChoice(vector<TreeNode *> &state, TreeNode *choice) {
state.pop_back();
}
/* 回溯算法：例题三 */
void backtrack(vector<TreeNode *> &state, vector<TreeNode *> &choices, vector<vector<TreeNode *>> &res) {
// 检查是否为解
if (isSolution(state)) {
// 记录解
recordSolution(state, res);
}
// 遍历所有选择
for (TreeNode *choice : choices) {
// 剪枝：检查选择是否合法
if (isValid(state, choice)) {
// 尝试：做出选择，更新状态
makeChoice(state, choice);
// 进行下一轮选择
vector<TreeNode *> nextChoices{choice->left, choice->right};
backtrack(state, nextChoices, res);
// 回退：撤销选择，恢复到之前的状态
undoChoice(state, choice);
}
}
}根据题意，我们在找到值为 7 的节点后应该继续搜索，因此需要将记录解之后的 return 语句删除。图对比了保留或删除 return 语句的搜索过程。
相比基于前序遍历的代码实现，基于回溯算法框架的代码实现虽然显得啰唆，但通用性更好。实际上，许多回溯问题可以在该框架下解决。我们只需根据具体问题来定义 state 和 choices ，并实现框架中的各个方法即可。
6.常用术语
为了更清晰地分析算法问题，我们总结一下回溯算法中常用术语的含义，并对照例题三给出对应示例，如表 所示。
常见的回溯算法术语
| 名词 | 定义 | 例题三 |
|---|---|---|
| 解（solution） | 解是满足问题特定条件的答案，可能有一个或多个 | 根节点到节点 7 的满足约束条件的所有路径 |
| 约束条件（constraint） | 约束条件是问题中限制解的可行性的条件，通常用于剪枝 | 路径中不包含节点 3 |
| 状态（state） | 状态表示问题在某一时刻的情况，包括已经做出的选择 | 当前已访问的节点路径，即 path 节点列表 |
| 尝试（attempt） | 尝试是根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解 | 递归访问左（右）子节点，将节点添加进 path ，判断节点的值是否为 7 |
| 回退（backtracking） | 回退指遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态 | 当越过叶节点、结束节点访问、遇到值为 3 的节点时终止搜索，函数返回 |
| 剪枝（pruning） | 剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率 | 当遇到值为 3 的节点时，则不再继续搜索 |
Tip
问题、解、状态等概念是通用的，在分治、回溯、动态规划、贪心等算法中都有涉及。
7.优点与局限性
回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。
然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。
- 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
- 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大。
即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种。
- 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
- 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。
8.回溯典型例题
回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题。
搜索问题：这类问题的目标是找到满足特定条件的解决方案。
- 全排列问题：给定一个集合，求出其所有可能的排列组合。
- 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集。
- 汉诺塔问题：给定三根柱子和一系列大小不同的圆盘，要求将所有圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上。
约束满足问题：这类问题的目标是找到满足所有约束条件的解。
- n 皇后：在 n×n 的棋盘上放置 n 个皇后，使得它们互不攻击。
- 数独：在 9×9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3×3 子网格中的数字不重复。
- 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。
组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。
- 0-1 背包问题：给定一组物品和一个背包，每个物品有一定的价值和重量，要求在背包容量限制内，选择物品使得总价值最大。
- 旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径。
- 最大团问题：给定一个无向图，找到最大的完全子图，即子图中的任意两个顶点之间都有边相连。
请注意，对于许多组合优化问题，回溯不是最优解决方案。
- 0-1 背包问题通常使用动态规划解决，以达到更高的时间效率。
- 旅行商是一个著名的 NP-Hard 问题，常用解法有遗传算法和蚁群算法等。
- 最大团问题是图论中的一个经典问题，可用贪心算法等启发式算法来解决。
题目一——46. 全排列 - 力扣（LeetCode）
说实话，这道题目就是暴力枚举，之间来n个for循环。但是这个非常容易出错。
其实这个回溯是有模板的，但是这个模板是有缺点的。我们更应该做到下面这些
- 画出决策树：越详细越好
绿色的x就是剪枝的意思！！
我们在每个结点干的东西是一样的。
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
- 按照决策树写代码
我们在解决这个问题的时候需要借助全局变量，还有dfs函数
注意：其实不一定需要搞成全局变量，也可以将其设置成函数参数，但是为了代码的简洁性，我们还是设置成全局变量即可
首先看全局变量；
- 我们必须得定义一个二维数组ret，因为我们需要返回一个二维数组来记录最终的结果
- 我们还需要设置一个path的二维数组，我们这个path就是来记录这个遍历的路径。然后遍历到叶子结点的时候，就把这个路径push_back进我们上面的ret
这两个是最基本的。
- 怎么实现剪枝？
我们来考虑一下剪枝怎么完成？也就是下面这个图里的绿色部分，我们要怎么做呢？
所以我们又需要一个bool数组check，这个数组专门来判断这个路径的数字是不是被使用过了，这个数组对应的是原数组的下标。
具体操作如下：
- 它给的是一个数组，我们创建一个和原数组等大的check数组，check数组元素的下标和原数组元素对应的下标是一一对应的。
- 我们是从前往后遍历的，每次遍历一个元素，我们就先把这个元素添加进path，然后将其在check数组里面对应位置的bool值设置为ture，然后我们就调用dfs继续寻找以这个元素为开头的全排列。
- 怎么实现回溯
说白了，回溯就是下面这个红色箭头
首先我们的path数组一定要pop_back最后一个元素（这里是3）
然后我们的check一定要将3对应的那个bool值改成false。
- 递归出口
直接判断：当遇到叶子结点的时候，直接将路径添加进结果即可。
到这原理就算是全部讲完了；
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[7]={false};
void dfs(vector<int>&nums)
{
if(nums.size()==path.size())//这说明原数组所有元素都出现过一遍了，此时就可以返回结果了
{
ret.push_back(path);
return;
}
for(int i=0;i<nums.size();i++)
{
if(check[i]==false)
{
path.push_back(nums[i]);
check[i]=true;
dfs(nums);
//回溯->恢复现场
path.pop_back();
check[i]=false;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
};我知道大家可能不太理解这个代码到底怎么写出来的，但是我们完完全全可以按照这个决策树来写代码
至于回溯
事实上，我知道大家不理解这个回溯，搞不明白这个回溯，但是事实上，我告诉你，不理解回溯就是不理解递归！不信的话可以看下面这个图
一旦调用这个dfs，就只会在那个递归出口出来，然后一直回溯到第一次调用这个dfs的时候
题目二——78. 子集 - 力扣（LeetCode）
其实这道题目是想告诉大家，这个回溯是没有什么固定的模板的，有相同的地方就是思考这种问题的思路是一样的
这个其实是高中的那个数学必修一的第一章吧。
2.1.解法一
好，接下来我们来看看怎么做？我们先按照下面这个步骤来解决题目即可
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
- 看着决策树写代码
首先来看决策树（注意下图里面的叉是不选的意思，勾是选的意思）
接下来我们来思考全局变量的问题
- 首先我们需要一个二维数组ret来记录我们最终的结果
- 然后我们需要一个path数组来记录我们选择的数字
- 那这里需不需要剪枝呢？
显然是不需要剪枝的，因为所有结果都是符合题目要求的。
- 那我们怎么知道当前选到哪个数字了呢？
我们可以给dfs函数设置一个参数i，代表当前i位置的数字选不选
- 如果选择的话，就path.push_back(nums[i])，dfs(nums,i+1)
- 如果不选择的话，直接dfs(nums,i+1)
接下来来考虑一下剪枝，回溯->恢复现场的情况
剪枝不存在
回溯呢？说白了回溯就是像下面这个红色箭头那样
我们只需要path.pop_back()即可
- 什么时候有递归出口呢
很简单啊，就是nums.size()==i的时候即可
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, int i) {
if (i == nums.size()) {
ret.push_back(path);
return;
}
// 我们先选
path.push_back(nums[i]);
dfs(nums, i + 1);
// 回溯->恢复现场
//这里一定是遍历到叶子结点才会执行的
path.pop_back();
// 然后再分析不选的情况
dfs(nums, i + 1);
//这里一定是遍历到叶子结点才会执行的
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
};
我知道大家可能对这个回溯有一点不理解，记住不理解回溯一定是不理解递归，我们画个图就理解了
一旦调用这个dfs，就只会在那个递归出口出来，然后一直回溯到第一次调用这个dfs的时候 。
2.2.解法二
这个还是一样的思路
- 决策树
- 全局变量
- dfs
- 回溯，剪枝，递归出口
首先看看这个版本的决策树怎么画
有没有发现这里每个结点都是我们想要的结果！！而解法一是只有叶子结点是我们的结果。
接下来我们来思考全局变量的问题
- 首先我们需要一个二维数组ret来记录我们最终的结果
- 然后我们需要一个path数组来记录我们选择的数字
接着来思考dfs函数体的设计
我们是需要一个函数参数pos来表示从原数组的哪里开始往后遍历寻找的
void dfs(vector<int>&nums,int pos)
{
....
for(int i=pos;i<nums.size();i++)
{
path.push_back(nums[i]);
dfs(nums,i+1);
//回溯->恢复现场
//这个时候一定到了叶子结点这里
....
}
...
}- 那这里需不需要剪枝呢？
这是需要剪枝的，因为我们只需要比我们选择的数字还要大的。但是这个for循环帮我们完成剪枝了。
- 递归出口
我们进入函数的时候，就将当前结点加入到path数组里面即可。
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, int pos) {
ret.push_back(path);
for(int i=pos;i<nums.size();i++)
{
path.push_back(nums[i]);
dfs(nums,i+1);
//回溯->恢复现场
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
};
题目三—— 1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
这道题不就是求子集吗？
好，接下来我们来看看怎么做？我们先按照下面这个步骤来解决题目即可
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
- 看着决策树写代码
首先看看这个版本的决策树怎么画
- 我们最后需要的是所有的子集都异或完之后的和，所以我们就直接使用一个全局变量sum来记录这个异或的和
- 然后我们还需要这个path来记录当前路径异或的值。
这题和上面的差不多，
- 接着来思考dfs函数头的设计
我们是需要一个函数参数pos来表示从原数组的哪里开始往后遍历寻找的
- 回溯-》恢复现场
所谓回溯，就是类似于下面这个红色箭头这个步骤
我们每遍历一层都会将该元素和path进行异或操作，那我们怎么让path回溯到上一层的状态呢？
很简单因为异或有下面这种性质
a ^ a = 0
a ^ 0 = a所以我们很快就能相到下面这个
b ^ a ^ a = b这样子是不是很好回溯了啊！！
- 那这里需不需要剪枝呢？
这是需要剪枝的，因为我们只需要比我们选择的数字还要大的。但是这个for循环帮我们完成剪枝了。所以我们就不必额外进行剪枝。
- 递归出口
我们进入函数的时候，就将当前结点异或进path即可。
class Solution {
public:
int sum;
int path;
void dfs(vector<int>& nums, int pos) {
sum += path;
for (int n = pos; n < nums.size(); n++) {
path ^= nums[n];
dfs(nums, n+1);
// 回溯
path ^= nums[n];
}
}
int subsetXORSum(vector<int>& nums) {
dfs(nums, 0);
return sum;
}
};我知道很多人不知道怎么写出来这个代码的，但是只要我们看着决策树就很容易写出这个代码
题目四——47. 全排列 II - 力扣（LeetCode）
这道题的核心是剪枝，其他的东西和上面那题是差不多的。我们先画出决策树
- 同一个结点的所有分枝中，相同的元素只能选择一次，其他的都要剪枝！
- 同一个数字只能使用一次
我们接下来有两种思考方式
- 只关心不合法的分支
- 只关心合法的分支
我们先看看只关心不合法的分支
我们可以使用一个bool数组check，专门用来存储原数组数字的使用情况，true代表使用过，false代表没有使用过，不合法的分支即check[i]==true
然后我们得实现同一个结点的所有分枝中，相同的元素只能选择一次
这样子我们必须得将数组进行排序，这个时候就判断nums[i]==nums[i-1]
但是这样子是不够的，因为我不知道这个nums[i-1]有没有被选择过啊，所以我们得加上这个判断条件check[i-1]==false&&i!=0
我们很快就能写出下面这个代码
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[9] = {false};
void dfs(vector<int>& nums, int pos) {
if (pos == nums.size()) {
ret.push_back(path);
return;
}
for (int n = 0; n < nums.size(); n++) {//看决策树，我们是遍历了所有元素的
if (check[n] == true ||
(n != 0 && nums[n] == nums[n - 1] && check[n - 1] == false)) {
continue;
}
path.push_back(nums[n]);
check[n]=true;
dfs(nums, pos + 1);
// 回溯
path.pop_back();
check[n]=false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
dfs(nums, 0);
return ret;
}
};
我们看看只关心合法的分支
我们可以使用一个bool数组check，专门用来存储原数组数字的使用情况，true代表使用过，false代表没有使用过
其实很简单，就是check[i]==false&&(i==0 || nums[i]!=nums[i-1] || check[i-1]=true)
check[i]==false：该元素没有被使用过
(i==0 || nums[i]!=nums[i-1] || check[i-1]==true)的意思是这3个条件里必须满足一个
- i==0（当前遍历的是原数组第一个元素，第一个元素可以大胆使用，因为不可能出现重复）
- nums[i]!=nums[i-1]（当前元素不是第一个元素，并且当前元素不等于前一个元素，这个是可以的）
- check[i-1]==true（当前元素不是第一个元素，并且当前元素等于前一个元素，但是前一个元素使用过）
注意：这个||的特别之处
- i==0 || nums[i]!=nums[i-1] || check[i-1]=true
- 如果i==0，那么后面的都不会进行判断
- 如果i!=0，才会接着往后面进行判断，这里存在一个先后的关系
我们很快就能写出第二种方法的代码
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[9] = {false};
void dfs(vector<int>& nums, int pos) {
if (pos == nums.size()) {
ret.push_back(path);
return;
}
for (int n = 0; n < nums.size(); n++) {//看决策树，我们是遍历了所有元素的
if (check[n] == false &&
(n == 0 || nums[n] != nums[n - 1] || check[n - 1] == true)) {
path.push_back(nums[n]);
check[n] = true;
dfs(nums, pos + 1);
// 回溯
path.pop_back();
check[n] = false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ret;
}
};
题目五——17. 电话号码的字母组合 - 力扣（LeetCode）
说实话，这道题其实是非常简单的。
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
- 看着决策树写出代码
我们先画决策树
有没有发现这个，其实我们只需要在叶子结点这里进行结果的保存即可
我不知道大家大家有没有发现，这个题目给的数组一定是按升序排列的，并且存在先后选择的关系，数字最小的一定先选择！！！
接着我们看看全局变量，
首先我们要解决数字和字符串的映射关系
我们如何解决这个问题？其实我们可以使用一个字符串数组，即vector<string>，然后下标0和1不保存字符串，在下标为2开始保存数字2对应的字符串，在下标为3的地方保存数字3对应的字符串
然后我们还需要一个path数组，记录我们选择过的字符即可，
我们需要一个ret数组来记录最终的结果
我们看看函数头的设计，其实看那个决策树的时候就应该想到，我们需要一个额外的参数来决定当前是选哪个数字对应的字符串。
- 回溯
就是返回的时候将path最后一个元素pop_back()
- 递归出口
就是当path.size()==nums.size()时，将path加入到这个ret数组即可
我们很快就能写出代码
class Solution {
public:
vector<string> ret;
string path;
vector<string> order = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(string& digits,
int pos) // 此时要选择dighits里面下标为pos的那个数字对应的字符串了
{
if (path.size() == digits.size()) {
ret.push_back(path);
return;
}
string tmp = order[digits[pos] - '0'];
for (int i = 0; i < tmp.size(); i++) {
path+=tmp[i];
dfs(digits, pos + 1);//注意这里，我们是选择完了dighits里面下标为pos
//的那个数字对应的字符串了，接着要去下标为pos+1的那里去接着选择了
// 回溯
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0)
{
return {};
}
dfs(digits, 0);
return ret;
}
};大家写代码的时候最好看着决策树写
题目六——22. 括号生成 - 力扣（LeetCode）
这个题意很容易理解
我们先考虑：什么是有效的括号？
其实叫我们搞有效的括号，实际上是给了我们2n个位置，然后每个位置只能放左括号或者右括号，然后还得满足上面那两个要求即可
- 左括号的数量==右括号的数量
- 左括号一定是n个，右括号一定是n个
- 从头开始的任意一个子串的左括号的数量都是>=右括号数量的
这样子就是一个有效的括号。
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
我们先画决策树
虽然这个决策树只画了一点点，但是我们很容易就发现了里面的两种剪枝的情况。
- 当我们添加左括号的时候需要去判断当前左括号的数量有没有超过n，即left>=n时，就停止添加左括号
- 当我们添加右括号的时候需要去判断当前左括号的数量是不是比右括号多，即right>=left，时就停止添加右括号
接着我们考虑一下全局变量
我们可以搞3个全局变量
- left：左括号数量
- right：右括号数量
- n：当前有多少对有效的括号
- path：我们每次遍历的
- ret：最终结果
回溯的时候就是path.pop_back()，然后需要将对应的left或者right--即可
递归出口就是叶子结点，即right==n的时候就可以
class Solution {
public:
int right;
int left;
int wn;
vector<string> ret;
string path;
void dfs() // 当前需要选哪个
{
if (right == wn) {
ret.push_back(path);
return;
}
// 选左括号
if (left < wn) {
path.push_back('(');
left++;
dfs();
path.pop_back();
left--;
}
//选右括号
if (right < left) {
path.push_back(')');
right++;
dfs();
path.pop_back();
right--;
}
}
vector<string> generateParenthesis(int n) {
wn = n;
dfs();
return ret;
}
};大家写代码的时候最好看着决策树写
题目七——77. 组合 - 力扣（LeetCode）
好像很简单啊。只不过要注意一下：{1,2}和{2,1}是等价的
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
我们先画决策树（越详细越好）
这里面的剪枝很详细了啊，只能从比最后一个元素大的开始往后选
我们还是在叶子结点这里回收即可。
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
int wn;
int wk;
void dfs(int pos) {
if (path.size() == wk) {
ret.push_back(path);
return;
}
for (int i = pos; i <= wn; i++) {
path.push_back(i);
dfs(i + 1);
// 回溯
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
wn = n;
wk = k;
dfs(1);
return ret;
}
};大家写代码的时候最好看着决策树写
题目八——494. 目标和 - 力扣（LeetCode）
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
我们先画决策树（越详细越好）
有没有感觉和题目二——子集那道题目好像啊？确实是，所以思路也和那题差不多
这里我们将使用两种方式来写代码
我们需要一个整型变量path
- path是全局变量（自己实现回溯）
- path不是全局变量（自动实现回溯）
来看看path是全局变量的时候的代码
class Solution {
public:
int ret;
int path;
int wtarget;
void dfs(vector<int>&nums,int pos)//本次是要选择nums数组下标为pos的数的正数还是负数
{
if(pos==nums.size())
{
if(path==wtarget)
{
ret++;
}
return;
}
//选择正数的情况
path+=nums[pos];
dfs(nums,pos+1);
//回溯
path-=nums[pos];
//选择负数的情况
path-=nums[pos];
dfs(nums,pos+1);
//回溯->恢复现场
path+=nums[pos];
}
int findTargetSumWays(vector<int>& nums, int target) {
wtarget=target;
dfs(nums,0);
return ret;
}
};
path不是全局变量的时候
class Solution {
public:
int ret;
int wtarget;
void dfs(vector<int>& nums, int pos, int path) {
if (pos == nums.size()) {
if (path == wtarget) {
ret++;
}
return;
}
// 选择正数的情况
dfs(nums, pos + 1, path + nums[pos]);
// 回溯（但在这里我们不需要显式地“回溯”path的值，
// 因为下一个递归调用会是一个全新的路径，
// 它不会受到当前递归调用中path值的影响。
// 但是，为了保持一致性，并且避免在递归之间共享状态，
// 我们通常会在注释中提到这一点。）
// 选择负数的情况
dfs(nums, pos + 1, path - nums[pos]);
// 注意：在这里我们实际上不需要再次“回溯”path的值，
// 因为上面的递归调用已经是一个全新的、独立的计算了。
// 但是，如果你习惯在递归之后恢复状态，你可以想象这里有一个
// “隐式的回溯”，即当上面的递归调用返回时，我们不需要做任何事，
// 因为当前递归调用的状态（包括path的值）已经“结束”了。
}
int findTargetSumWays(vector<int>& nums, int target) {
wtarget = target;
dfs(nums, 0, 0); // 从位置0开始，初始路径和为0
return ret;
}
}; 
题目九—— 39. 组合总和 - 力扣（LeetCode）
9.1.解法一
这道题题意很简单啊，就不多讲了。但是要注意[2,2,3]和[3,2,2]是一样的。
接下来我将讲解两种办法，主要是告诉大家，没有绝对的模板，但是有固定的步骤
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
- 按照决策树写代码
我们来看看决策树
我们直接看代码
使用全局变量版本
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
int cursum;
int wtarget;
void dfs(vector<int>& nums, int pos) // 从nums数组的pos下标位置开始选择
{
if (wtarget == cursum) {
ret.push_back(path);
return;
}
if (cursum > wtarget || pos == nums.size()) {
return;
}
for (int i = pos; i < nums.size(); i++) {
path.push_back(nums[i]);
cursum += nums[i];
dfs(nums, i);
// 回溯
cursum -= nums[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
wtarget = target;
dfs(candidates, 0);
return ret;
}
};
不使用全局变量，使用函数参数版本
class Solution {
public:
// 存储所有满足条件的组合的二维向量
vector<vector<int>> ret;
// 存储当前正在构建的组合的一维向量
vector<int> path;
// 存储目标和
int wtarget;
// 深度优先搜索函数，用于找出所有满足条件的组合
// nums: 给定的候选数字数组
// pos: 当前搜索的起始位置
// cursum: 当前组合的和
void dfs(vector<int>& nums, int pos, int cursum)
{
// 如果当前组合的和等于目标和，则将当前组合添加到结果中
if (wtarget == cursum) {
ret.push_back(path);
return;
}
// 如果当前组合的和已经大于目标和，或者已经遍历完候选数字数组，则直接返回
if (cursum > wtarget || pos == nums.size()) {
return;
}
// 从当前位置开始遍历候选数字数组
for (int i = pos; i < nums.size(); i++) {
// 将当前数字添加到组合中
path.push_back(nums[i]);
// 递归调用，继续搜索下一个数字，同时更新当前组合的和
// 注意：这里传递的是i而不是i + 1，意味着允许在同一个组合中重复使用相同的数字
dfs(nums, i, cursum + nums[i]);
// 回溯：移除刚刚添加的数字，以便尝试其他可能的组合
path.pop_back();
}
}
// 主函数，用于找出所有满足条件的组合并返回结果
// candidates: 给定的候选数字数组
// target: 目标和
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
wtarget = target; // 初始化目标和
dfs(candidates, 0, 0); // 从数组的第一个元素开始搜索，初始和为0
return ret; // 返回所有满足条件的组合
}
}; 
9.2.解法二
我们这里其实可以画另外一种决策树，我们按原数组里面元素的先后顺序来依次考虑每个元素应该出现几次
这里特别注意回溯的时候，我们是枚举完所有叶子结点的时候再进行回溯的，这个时候就非常方便
class Solution {
int aim;
vector<int> path;
vector<vector<int>> ret;
public:
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
aim = target;
dfs(nums, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int sum) {
if (sum == aim) {
ret.push_back(path);
return;
}
if (sum > aim || pos == nums.size())
return;
//枚举个数
for (int k = 0; k * nums[pos] + sum <= aim; k++) {
if (k!=0)
{
path.push_back(nums[pos]);
}
dfs(nums, pos + 1, sum + k * nums[pos]);
}
//恢复现场
for (int k = 1; k * nums[pos] + sum <= aim; k++) {
path.pop_back();
}
}
};
题目十——784. 字母大小写全排列 - 力扣（LeetCode）
还是熟悉的套路，先画决策树
看起来好像很简单哦！！
- 怎么把大写字母转变成小写字母？
小写字母的ascii码值比大写字母的ascii码值大32
我们很快就能写出下面这个代码
class Solution {
public:
vector<string> ret;
string path;
void change(string& s, int pos) {
// 当前字符是数字
if (s[pos] >= '0' && s[pos] <= '9') {
path += s[pos];
}
// 当前字符是大写字符
if (s[pos] >= 'A' && s[pos] <= 'Z') {
path += (char)(s[pos] + 32);
} else if (s[pos] >= 'a' && s[pos] <= 'z') // 当前字符是小写字符
{
path += (char)(s[pos] - 32);
}
}
void dfs(string& s, int pos) {
if (path.size() == s.size()) {
ret.push_back(path);
return;
}
// 不改变的情况
path += s[pos];
dfs(s, pos + 1);
// 回溯
path.pop_back();
// 改变的情况——>只有不是数字的情况才需要改变
// 改变
if (s[pos] < '0' || s[pos] > '9') {
change(s, pos);
dfs(s, pos + 1);
// 回溯
path.pop_back();
}
}
vector<string> letterCasePermutation(string s) {
dfs(s, 0);
return ret;
}
};
题目十一—— 526. 优美的排列 - 力扣（LeetCode）
这题还是一样的思路。先画决策树啊！
class Solution {
public:
int ret; // 用于存储最终的结果，即满足条件的排列数
int wn; // 存储输入的数字n，表示有1到n的数字需要排列
bool check[16] = {false}; // 用于标记数字是否被使用过，因为n最大为15（题目未说明，但从数组大小推测），初始化为false表示都未使用
// 深度优先搜索函数，pos表示当前正在尝试放置的数字位置
void dfs(int pos) {
// 当已经尝试完所有的位置，即找到一个满足条件的排列
if (pos == wn + 1) {
ret++; // 满足条件的排列数加一
return;
}
// 遍历1到n的所有数字，尝试将它们放在当前位置pos
for (int i = 1; i <= wn; i++) {
// 检查数字i是否未被使用过，并且满足条件：i能被pos整除或者pos能被i整除
// 这个条件确保了当前数字i可以放在位置pos上（根据题目的某种隐含规则，可能是数字i和位置pos有某种数学关系）
if (check[i] == false && (pos % i == 0 || i % pos == 0)) {
check[i] = true; // 标记数字i为已使用
dfs(pos + 1); // 递归尝试下一个位置
// 回溯：将数字i标记为未使用，以便尝试其他可能的数字放在当前位置
check[i] = false;
}
}
}
// 外部接口函数，计算并返回满足条件的排列数
int countArrangement(int n) {
wn = n; // 设置需要排列的数字范围
dfs(1); // 从第一个位置开始尝试排列
return ret; // 返回计算出的满足条件的排列数
}
};
题目十二——51. N 皇后 - 力扣（LeetCode）
这道题绝对是回溯中的经典中的经典！！！
- 我们要保证每一行，每一列都有皇后。
- 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子（注意皇后的攻击范围是四条直线）
我们还是使用之前的方法
其实在解决回溯这种问题的时候，我们就需要按照下面这两步来
- 画出决策树
- 思考全局变量，dfs函数，剪枝，回溯，递归出口
- 按照决策树写代码
首先我们看决策树怎么画
决策树其实是有两种的，
- 第一种就是一个小格子，一个小格子选（这种其实是有点麻烦的）
- 第二种是一行一行选
我们只看一行一行的那种
看起来是不是很简单啊？
其实这里特别重要的是剪枝和代码能力
- 如何剪枝？
剪枝就是考虑当前位置能否放上皇后？
我们可以使用类似哈希表的策略，我们使用3个数组就能完成这个剪枝
- bool col[n]：这一列是否有皇后
我们接着看斜对角线
我们发现n*n的矩阵，会有2*n-1条主对角线。每条主对角线的y-x的值都是固定的。但是我们发现右边部分y-x是负数，所以我们让左右部分各相加一个n，即每条主对角线的y-x+n是一个定值。
所以我们可以开辟一个数组，下标对应y-x+n，值存true或者false。
接着来看副对角线的情况
我们很快就能发现y+x是一个定值，而且y+x是>=0的。
我们很快就能写出代码
class Solution {
bool checkCol[10], checkDig1[20], checkDig2[20];
vector<vector<string>> ret;
vector<string> path;
int n;
public:
vector<vector<string>> solveNQueens(int _n) {
n = _n;
path.resize(n);
for(int i = 0; i < n; i++)
path[i].append(n, '.');
dfs(0);//从第一层开始
return ret;
}
void dfs(int pos)
{
if(pos==n)//越界了
{
ret.push_back(path);
return;
}
for(int i=0;i<n;i++)
{
if(checkCol[i]==false&&checkDig1[pos-i+n]==false&&checkDig2[pos+i]==false)
//判断当前点能不能放皇后
{
path[pos][i]='Q';
checkCol[i]=true;
checkDig1[pos-i+n]=true;
checkDig2[pos+i]=true;
dfs(pos+1);
//回溯
path[pos][i]='.';
checkCol[i]=false;
checkDig1[pos-i+n]=false;
checkDig2[pos+i]=false;
}
}
}
};
非常简单！！
题目十三——36. 有效的数独 - 力扣（LeetCode）
什么是数独？
其实这个思想和n皇后的那道差不多。我们可以使用
- bool row[r][w]：代表第r行里面是不是出现过数字w
- bool col[c][w]：代表第c列里面是不是出现过数字w
接下来来搞我们的3*3小方格。其实特别巧妙
我们可以搞一个数组bool grid[3][3][w]，前面的[3][3]代表是3*3的小方格，我们的[w]是代表有没有出现过数字w。
接下来来思考下标映射的关系
其实特别巧妙，我们只需要让下标/3即可知道在哪一个小方格里面。
class Solution {
// 用于存储每行是否已有某个数字（1-9）的布尔数组
bool row[9][10]; // 9行，10列（第10列未使用，仅为了方便索引从1到9）
// 用于存储每列是否已有某个数字的布尔数组
bool col[9][10]; // 9列，10列（同上）
// 用于存储每个3x3子网格是否已有某个数字的布尔数组
// 3x3表示有3个3x3的子网格，10列表示数字1-9（索引1-9），第10列未使用
bool grid[3][3][10];
public:
// 检查给定的数独棋盘是否有效的函数
bool isValidSudoku(vector<vector<char>>& board) {
// 初始化行、列和3x3子网格的布尔数组为false
// 这里没有显式初始化代码，因为C++的全局或静态数组会被自动初始化为0（即false）
// 遍历数独棋盘的每个单元格
for (int r = 0; r < 9; r++) { // r表示行
for (int c = 0; c < 9; c++) { // c表示列
// 如果当前单元格不是空的（即包含数字）
if (board[r][c] != '.') {
// 将字符数字转换为整数（'1'-'9' -> 1-9）
int tmp = board[r][c] - '0';
// 检查当前数字是否已经在当前行、列或3x3子网格中出现过
if (row[r][tmp] == true || col[c][tmp] == true ||
grid[r / 3][c / 3][tmp] == true) {
// 如果已经出现过，则返回false，表示数独无效
return false;
}
// 如果没有出现过，则标记当前数字在当前行、列和3x3子网格中已出现过
row[r][tmp] = col[c][tmp] = grid[r / 3][c / 3][tmp] = true;
}
}
}
// 如果所有检查都通过，则返回true，表示数独有效
return true;
}
};
题目十四——37. 解数独 - 力扣（LeetCode）
这题简直和上一道题目是一模一样的思路，我们很快就能写出下面这个代码
class Solution {
public:
// 用于存储每行是否已有某个数字（1-9）的布尔数组
bool row[9][10]; // 9行，10列（第10列未使用，仅为了方便索引从1到9）
// 用于存储每列是否已有某个数字的布尔数组
bool col[9][10]; // 9列，10列（同上）
// 用于存储每个3x3子网格是否已有某个数字的布尔数组
// 3x3表示有3个3x3的子网格，10列表示数字1-9（索引1-9），第10列未使用
bool grid[3][3][10];
void dfs(vector<vector<char>>&board)
{
for(int r=0;r<9;r++)
{
for(int c=0;c<9;c++)
{
if(board[r][c]=='.')
{
for(int i=1;i<=9;i++)
{
if(row[r][i]==false&&col[c][i]==false&&grid[r/3][c/3][i]==false)
{
board[r][c]='0'+i;
row[r][i]=col[c][i]=grid[r/3][c/3][i]=true;
dfs(board);
//回溯
board[r][c]='.';
row[r][i]=col[c][i]=grid[r/3][c/3][i]=false;
}
}
}
}
}
}
void solveSudoku(vector<vector<char>>& board) {
for(int r=0;r<9;r++)
{
for(int c=0;c<9;c++)
{
if(board[r][c]!='.')
{
int tmp=board[r][c]-'0';
row[r][tmp]=true;
col[c][tmp]=true;
grid[r/3][c/3][tmp]=true;
}
}
}
dfs(board);
}
};但是却出现了下面这个情况
这说明我们的代码有问题哦！！
其实这就是不画决策树的后果！！ 我们并没有设置函数递归出口
我们要在哪里设置递归出口呢？
很显然就是dfs返回的那个时候
class Solution {
public:
// 成员变量，用于存储数独状态
// 布尔数组，记录每行是否已有某个数字（1-9）
bool row[9][10]; // 9行，10列（第10列未使用，索引从0到9，但数字索引从1到9）
// 布尔数组，记录每列是否已有某个数字（1-9）
bool col[9][10]; // 9列，10列（同上）
// 布尔数组，记录每个3x3子网格是否已有某个数字（1-9）
// 3x3x10表示有3个3x3的子网格，每个子网格有10种可能的数字（1-9，索引1-9），第10列未使用
bool grid[3][3][10];
// 深度优先搜索函数，尝试填充数独网格
// 返回true表示成功找到一个解，返回false表示当前路径不可行
bool dfs(vector<vector<char>>& board)
{
// 遍历数独网格的每个位置
for(int r = 0; r < 9; r++)
{
for(int c = 0; c < 9; c++)
{
// 如果当前位置是空白的（'.'）
if(board[r][c] == '.')
{
// 尝试填入数字1到9
for(int i = 1; i <= 9; i++)
{
// 检查当前数字是否在当前行、列和3x3子网格中都没有出现过
if(row[r][i] == false && col[c][i] == false && grid[r/3][c/3][i] == false)
{
// 临时填入数字
board[r][c] = '0' + i;
// 更新行、列和子网格的状态
row[r][i] = col[c][i] = grid[r/3][c/3][i] = true;
// 递归地尝试填充下一个空白位置
if(dfs(board) == true) // 如果找到一个解，直接返回true
{
return true;
}
// 回溯：撤销当前位置的数字，并恢复行、列和子网格的状态
board[r][c] = '.';
row[r][i] = col[c][i] = grid[r/3][c/3][i] = false;
}
}
// 如果1-9都试完了，还是没有找到解，返回false
// 这意味着当前空白位置无法填入任何合法数字，当前路径不可行
return false;
}
}
}
// 如果所有空白位置都被成功填充，返回true
// 这意味着我们找到了一个完整的数独解
return true;
}
// 解决数独问题的主函数
void solveSudoku(vector<vector<char>>& board) {
// 初始化行、列和子网格的状态
for(int r = 0; r < 9; r++)
{
for(int c = 0; c < 9; c++)
{
// 如果当前位置不是空白的
if(board[r][c] != '.')
{
int tmp = board[r][c] - '0'; // 将字符数字转换为整数数字
// 更新行、列和子网格的状态
row[r][tmp] = true;
col[c][tmp] = true;
grid[r/3][c/3][tmp] = true;
}
}
}
// 开始深度优先搜索
dfs(board);
}
};
题目十五——79. 单词搜索 - 力扣（LeetCode）
这个题意特别简单啊，我们还是按照老样子来解决这个问题。
我们得先有一个策略，比如下面
我们仔细看这个，我们首先得先找到A吧。
找到A之后，我们就在它的上下左右去寻找字符B。但是这次没找到B，只能说明这个位置的A是不符合条件的。我们直接停止寻找。
我们接着寻找下一个位置的A.
但是从这个位置的A找发现有两个B。那我们先走哪一个呢？我们可以一个一个来找即可。
就这样子一直使用到最后
好，现在就这样子。我们的算法思想已经出来了。我们可以将它抽象起来，就是一个深度优先遍历。
我们画一个决策树。
是不是很简单啊?
我们看一下每一个结点干什么，我们发现都是在你给我一个字符的位置，我从这个字符的位置的上下左右匹配原字符串的下一个字符。
递归函数设计：
bool dfs(int x,int y,int step,<vector>& board,
string word, vector>& vis, int & n, int & m, int & len)参数：
- x（当前需要进⾏处理的元素横坐标）
- y（当前需要进⾏处理的元素横坐标）
- step（当前已 经处理的元素个数）
- word（当前的字符串状态）；
- 返回值：当前坐标元素作为字符串中下标step的元素出现是否可以找到成⽴的字符串。
- 函数作⽤：判断当前坐标的元素作为字符串中下标step的元素出现时，向四个⽅向传递，查找是否存 在路径结果与字符串相同。
这里要特别注意：不能走重复的路
怎么规避这么一种情况？很简单，就使用一个bool数组来记录哪个位置的字符一旦使用过。
这个解法大家可能觉得浪费空间，其实我们还有下一种解法，就是修改原始数组
- 特别地，如果使⽤将当前遍历到的字符赋值为空格，并在回溯时恢复为原来的字⺟的⽅法，则在递 归时不会重复遍历当前元素，可达到不使⽤标记数组的⽬的。
递归函数流程：
1. 遍历每个位置，标记当前位置并将当前位置的字⺟作为⾸字⺟进⾏递归，并且在回溯时撤回标记。
2. 在每个递归的状态中，我们维护⼀个步数step，表⽰当前已经处理了⼏个字⺟。
- 若当前位置的字⺟与字符串中的第step个字⺟不相等，则返回false。
- 若当前step的值与字符串⻓度相等，表⽰存在⼀种路径使得word成⽴，返回true。
3. 对当前位置的上下左右四个相邻位置进⾏递归，若递归结果为true，则返回true。
4. 若相邻的四个位置的递归结果都为false，则返回false。
我们很快就能写出代码
class Solution {
public:
// 定义一个7x7的布尔数组，用于记录网格中的字符是否已被访问过
// 注意：在实际应用中，这个数组的大小应该根据网格的实际大小来动态分配
bool check[7][7];
// 定义四个方向的偏移量，分别对应上、下、左、右
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
// 深度优先搜索函数
bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos) {
// 如果已经搜索到单词的末尾，说明找到了完整的单词
if (pos == word.size()) {
return true;
}
// 遍历四个方向
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
// 检查新坐标是否在网格范围内，字符是否匹配，以及该位置是否未被访问过
if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size()
&& board[x][y] == word[pos] && check[x][y] == false) {
// 标记该位置为已访问
check[x][y] = true;
// 递归地在新的位置继续搜索下一个字符
if (dfs(board, x, y, word, pos + 1) == true) {
return true;
}
// 回溯：如果在新位置没有找到完整的单词，则将该位置重新标记为未访问
check[x][y] = false;
}
}
// 如果在所有方向都没有找到完整的单词，则返回false
return false;
}
// 判断单词是否存在于网格中
bool exist(vector<vector<char>>& board, string word) {
// 遍历整个网格，寻找单词的第一个字符
for (int m = 0; m < board.size(); m++) {
for (int n = 0; n < board[0].size(); n++) {
if (board[m][n] == word[0]) {
// 标记该位置为已访问（虽然这里只是临时访问，但为了保持一致性，还是进行标记）
check[m][n] = true;
// 从该位置开始，使用深度优先搜索寻找完整的单词
if (dfs(board, m, n, word, 1) == true) {
return true;
}
// 回溯：如果在这个起始位置没有找到完整的单词，则将该位置重新标记为未访问（实际上这行代码是多余的，因为check数组在dfs中已经被回溯）
// 但为了保持代码的清晰性和一致性，这里还是保留了这行代码
check[m][n] = false;
}
}
}
// 如果在整个网格中都没有找到单词，则返回false
return false;
}
};
题目十六——1219. 黄金矿工 - 力扣（LeetCode）
这个特别像刚刚做的单词搜索啊！！
- 每个单元格只能被开采（进入）一次。
- 0不能进去
特别注意这个题目不能回退！！！
全局变量版本（有缺陷性）
class Solution {
public:
int ret; // 用于存储找到的最大黄金数量
int path; // 当前路径上累积的黄金数量
bool check[16][16]={false}; // 用于标记某个位置是否已经被访问过
// 定义四个方向的移动向量
int dx[4] = {0, 0, -1, 1}; // 上下左右移动时 x 的变化量
int dy[4] = {1, -1, 0, 0}; // 上下左右移动时 y 的变化量
// 深度优先搜索函数
void dfs(vector<vector<int>>& grid, int i, int j) {
// 更新最大黄金数量（这里可能会因为 path 的累积而得到错误结果）
ret = max(ret, path);
// 尝试向四个方向移动
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
// 检查新位置是否合法、是否有黄金且未被访问过
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() &&
grid[x][y] != 0 && check[x][y] == false) {
// 累积当前路径的黄金数量
path += grid[x][y];
// 标记当前位置为已访问
check[x][y] = true;
// 递归搜索下一个位置
dfs(grid, x, y);
// 回溯：撤销对当前位置的访问标记，并减去累积的黄金数量
// 注意：这里撤销的是对当前位置的黄金数量的累积，但 path 仍然包含了之前路径的累积
path -= grid[x][y];
check[x][y] = false;
}
}
}
// 主函数：获取网格中的最大黄金数量
int getMaximumGold(vector<vector<int>>& grid) {
// 遍历网格中的每个位置
for (int r = 0; r < grid.size(); r++) {
for (int c = 0; c < grid[0].size(); c++) {
// 如果当前位置有黄金
if (grid[r][c] != 0) {
// 初始化当前路径的黄金数量为当前位置的黄金数量
path = grid[r][c];
// 标记当前位置为已访问（这里其实没必要，因为 dfs 内部会再次设置）
// 但由于 check 是成员变量且需要在 dfs 结束后恢复，这里的设置是必要的
check[r][c] = true;
// 从当前位置开始深度优先搜索
dfs(grid, r, c);
// 回溯：撤销对当前位置的访问标记（这里实际上是多余的，因为 dfs 内部已经撤销了）
// 但由于 check 是成员变量且需要在后续遍历中保持未访问状态，这里的设置是必要的
check[r][c] = false;
}
}
}
// 返回找到的最大黄金数量
return ret;
}
};大家特别注意这个path变量每一次都需要更新成grid[r][c]之后才可以调用dfs函数
局部变量版本
class Solution {
public:
int ret; // 用于存储全局的最大黄金数量
// 下面的 path 变量在原始代码中作为类成员变量可能会导致问题，
// 因为它在多次 dfs 调用中共享且未被正确重置。
// 但在下面的代码中，我们将其作为 dfs 函数的参数传递，因此不再需要作为类成员。
bool check[16][16] = {false}; // 用于标记网格中的单元格是否已被访问过
int dx[4] = {0, 0, -1, 1}; // 右移、左移、下移、上移的 x 坐标变化量
int dy[4] = {1, -1, 0, 0}; // 右移、左移、下移、上移的 y 坐标变化量
// 深度优先搜索函数，增加了 path 参数来跟踪当前路径上的黄金数量
void dfs(vector<vector<int>>& grid, int i, int j, int path) {
// 更新全局最大黄金数量
ret = max(ret, path);
// 尝试四个方向的移动
for (int k = 0; k < 4; k++) {
int x = i + dx[k]; // 计算新位置的 x 坐标
int y = j + dy[k]; // 计算新位置的 y 坐标
// 检查新位置是否在网格内、是否为非零单元格且未被访问过
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() &&
grid[x][y] != 0 && check[x][y] == false) {
// 标记该单元格为已访问
check[x][y] = true;
// 递归调用 dfs，并将当前黄金数量加上新位置的黄金数量
dfs(grid, x, y, path + grid[x][y]);
// 回溯：取消标记，因为该路径没有导致更大的黄金数量
check[x][y] = false;
}
}
}
// 主函数，用于找到网格中能够收集到的最大黄金数量
int getMaximumGold(vector<vector<int>>& grid) {
// 初始化全局最大黄金数量为 0
ret = 0;
// 遍历网格中的每个单元格
for (int r = 0; r < grid.size(); r++) {
for (int c = 0; c < grid[0].size(); c++) {
// 如果当前单元格包含黄金且未被访问过
if (grid[r][c] != 0) {
// 标记该单元格为已访问（这一步实际上在这个特定算法中是多余的，
// 因为 dfs 内部会管理访问状态，但保留它可以帮助理解代码）
check[r][c] = true;
// 从当前单元格开始深度优先搜索
dfs(grid, r, c, grid[r][c]);
// 回溯：取消标记（同样，这一步在这个特定算法中是多余的）
check[r][c] = false;
}
}
}
// 返回找到的最大黄金数量
return ret;
}
};
题目十七——980. 不同路径 III - 力扣（LeetCode）
这个题意好像特别简单啊。使用DFS来解决是相当简单的。
我们可以先遍历数组找到起始位置1，然后就从那里开始遍历各种到达2的路径，最后再判断一下有哪些路径合法即可。
那我们怎么知道哪些路径是合法的？很简单啊，
我们先遍历整个数组找到-1的个数有多少个，然后合法路径的step=整个数组所有元素的个数-2（1和2各一个）-(-1的个数）。
然后我们再使用一个变量count来记录这个遍历过程走过的步数。
很简单啊！！！
全局变量版本
class Solution {
// 成员变量
int ret; // 存储从起点到终点的唯一路径总数
int step; // 从起点到终点（包括终点而且包括起点）需要经过的空地和终点的总数
int count; // 当前路径已经经过的空地的数量（包括起点）
bool check[21][21]; // 标记某个位置是否已经被访问过的二维布尔数组
int dx[4]={0,0,-1,1}; // 四个方向（右、左、下、上）的列偏移量
int dy[4]={1,-1,0,0}; // 四个方向（右、左、下、上）的行偏移量
public:
// 深度优先搜索（DFS）方法
void dfs(vector<vector<int>>& grid, int i, int j) {
// 如果当前位置是终点
if(grid[i][j]==2) {
// 如果当前路径的空地数量等于从起点到终点需要经过的总空地数量
if(count==step) {
// 找到了一条有效路径，增加路径总数
ret++;
}
// 终点处理完毕，返回
return;
}
// 遍历四个方向
for(int k=0; k<4; k++) {
int x=i+dx[k], y=j+dy[k]; // 计算新位置的坐标
// 检查新位置是否在迷宫范围内、是否未被访问过、是否是空地或终点
if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size()
&& check[x][y]==false && grid[x][y]!=-1) {
//特别注意起点那个位置已经conut++了
// 标记grid[x][y]为已访问，并增加经过的空地数量
count++;
check[x][y]=true;
// 递归调用dfs，继续搜索
dfs(grid, x, y);
// 回溯：撤销对当前位置的访问标记，并减少经过的空地数量
count--;
check[x][y]=false;
}
}
}
// 计算唯一路径的方法
int uniquePathsIII(vector<vector<int>>& grid) {
// 计算从起点到终点需要经过的总空地数量（不包括起点，但包括终点）
for(int i=0; i<grid.size(); i++) {
for(int n=0; n<grid[0].size(); n++) {
//这里将终点和起点都算进去了
if(grid[i][n]!=-1) {
step++;
}
}
}
// 寻找起点的位置，并从该位置开始调用dfs方法
for(int i=0; i<grid.size(); i++) {
for(int n=0; n<grid[0].size(); n++) {
if(grid[i][n]==1) {
// 起点位置，初始化count为1（因为起点也算一个经过的位置）
count=1;
// 标记起点为已访问
check[i][n]=true;
// 从起点开始深度优先搜索
dfs(grid, i, n);
// 注意：这里不需要再次重置check[i][n]为false，因为不需要，开始的情况只有1种
}
}
}
// 返回唯一路径的总数
return ret;
}
};
函数参数版本
class Solution {
// 成员变量
int ret; // 存储从起点到终点的唯一路径总数
int step; // 从起点到终点（包括终点而且包括起点）需要经过的空地和终点的总数
int count; // 当前路径已经经过的空地的数量（包括起点）
bool check[21][21]; // 标记某个位置是否已经被访问过的二维布尔数组
int dx[4]={0,0,-1,1}; // 四个方向（右、左、下、上）的列偏移量
int dy[4]={1,-1,0,0}; // 四个方向（右、左、下、上）的行偏移量
public:
// 深度优先搜索（DFS）方法
void dfs(vector<vector<int>>& grid, int i, int j,int count) {
// 如果当前位置是终点
if(grid[i][j]==2) {
// 如果当前路径的空地数量等于从起点到终点需要经过的总空地数量
if(count==step) {
// 找到了一条有效路径，增加路径总数
ret++;
}
// 终点处理完毕，返回
return;
}
// 遍历四个方向
for(int k=0; k<4; k++) {
int x=i+dx[k], y=j+dy[k]; // 计算新位置的坐标
// 检查新位置是否在迷宫范围内、是否未被访问过、是否是空地或终点
if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size()
&& check[x][y]==false && grid[x][y]!=-1) {
check[x][y]=true;
// 递归调用dfs，继续搜索
dfs(grid, x, y,count+1);
// 回溯：撤销对当前位置的访问标记，并减少经过的空地数量
check[x][y]=false;
}
}
}
// 计算唯一路径的方法
int uniquePathsIII(vector<vector<int>>& grid) {
// 计算从起点到终点需要经过的总空地数量（不包括起点，但包括终点）
for(int i=0; i<grid.size(); i++) {
for(int n=0; n<grid[0].size(); n++) {
//这里将终点和起点都算进去了
if(grid[i][n]!=-1) {
step++;
}
}
}
// 寻找起点的位置，并从该位置开始调用dfs方法
for(int i=0; i<grid.size(); i++) {
for(int n=0; n<grid[0].size(); n++) {
if(grid[i][n]==1) {
// 标记起点为已访问
check[i][n]=true;
// 从起点开始深度优先搜索
dfs(grid, i, n,1);
}
}
}
// 返回唯一路径的总数
return ret;
}
}; 
原文地址：https://blog.csdn.net/2301_80224556/article/details/144273475
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！