• • 思路

• 代码实现

前言

---

回溯算法，之前也是写过的，感觉还不错。但是之前分成两篇写了，现在重新整理一下，顺便我自己也回顾一下。

递归

---

要玩得转回溯算法，递归思想就要融入骨子里。

正好早上我整理了一篇递归相关的，不妨看一下：【C++】算法集锦（2）：递归

N叉树的遍历

---

我们从N叉树的遍历入手，来看一下回溯算法。

思考一下二叉树的回顾一下二叉树的遍历方式：

前序遍历 - 首先访问根节点，然后遍历左子树，最后遍历右子树；

中序遍历 - 首先遍历左子树，然后访问根节点，最后遍历右子树；

后序遍历 - 首先遍历左子树，然后遍历右子树，最后访问根节点；

层序遍历 - 按照从左到右的顺序，逐层遍历各个节点。

N 叉树的中序遍历没有标准定义，中序遍历只有在二叉树中有明确的定义。

我们跳过 N 叉树中序遍历的部分。

节点设计

class Node {

public:

int val;

vector<Node*> children; //注意，这里不再是左右子节点了

Node() {}

Node(int _val) {

val = _val;

}

Node(int _val, vector<Node*> _children) {

val = _val;

children = _children;

}

};

---

N叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历。

class Solution {

public:

void preorderDFS(Node* root, int index, vector& ret) {

if (root == NULL)

return;

ret.push_back(root->val);

int sz = (root->children).size();

while (index < sz) {

preorderDFS(root->children[index], 0, ret); //认真捋一下这一步

index += 1;

}

}

vector preorder(Node* root) {

vector ret;

preorderDFS(root, 0, ret);

return ret;

}

};

修改于 2021.8.22：

//经测试，这段代码更简洁：

void preorder(Node* node) {

cout << “value：” << node->val << endl;

for (Node* n : node->children) {

preorder(n);

}

return;

}

后序我就不调了吧，一行代码位置的事情。

---

后序遍历

给定一个 N 叉树，返回其节点值的后序遍历。

class Solution {

public:

void postorderDFS(Node* root, int index, vector& ret) {

if (root == NULL)

return;

int sz = (root->children).size();

while (index < sz) {

postorderDFS(root->children[index], 0, ret);

index += 1;

}

ret.push_back(root->val);

}

vector postorder(Node* root) {

vector ret;

postorderDFS(root, 0, ret);

return ret;

}

};

---

层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

class Solution {

public:

vector<vector> result;

void dfs(Node* root, int dep){

if(!root) return;

if(dep == result.size()) result.emplace_back();

result[dep].push_back(root->val);

auto children = root->children;

for(auto ele:children){

dfs(ele, dep+1);

}

}

vector<vector> levelOrder(Node* root) {

dfs(root, 0);

return result;

}

};

---

岛屿最大面积、八皇后问题、括号生成感觉比较简单，所以思路讲的就比较简陋，适合入门练手，建议看其他题目的讲解（全排列那题）。

---

回溯例题精讲

---

岛屿最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],

[0,0,0,0,0,0,0,1,1,1,0,0,0],

[0,1,1,0,1,0,0,0,0,0,0,0,0],

[0,1,0,0,1,1,0,0,1,0,1,0,0],

[0,1,0,0,1,1,0,0,1,1,1,0,0],

[0,0,0,0,0,0,0,0,0,0,1,0,0],

[0,0,0,0,0,0,0,1,1,1,0,0,0],

[0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/max-area-of-island

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题其实我自己做出来了，把它放在第一题嘛，我觉得因为它是比较简单的。

从头开始遍历，遇到“1”就展开上下左右搜索，搜空了就回溯，在搜索过程中计数，并将搜索到的位置全部置0，防止二次污染。

代码实现

int checkIsland(vector<vector>& grid, int x, int y) {

int count = 0;

if (grid[x][y] == 0)

return count;

else {

grid[x][y] = 0;

count++;

//上

if (x - 1 >= 0)

count += checkIsland(grid, x - 1, y);

//右

if ((y + 1) < grid[0].size())

count += checkIsland(grid, x, y + 1);

//下

if ((x + 1) < grid.size())

count += checkIsland(grid, x + 1, y);

//左

if ((y - 1) >= 0)

count += checkIsland(grid, x, y - 1);

}

return count;

}

int maxAreaOfIsland(vector<vector>& grid) {

if (grid.size() == 0)

return 0;

int max = 0;

for (int i = 0; i < grid.size(); i++) {

for (int j = 0; j < grid[0].size(); j++) {

int temp = checkIsland(grid, i, j);

if (temp > max)

max = temp;

}

}

}

return max;

}

---

八皇后问题

八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？

思路

将每一个棋子放在当前列的最前端，再放下一个棋子。

如果下一个棋子没地方放了，就回溯到前一个棋子，将其往后一个适宜位置挪动。

具体思路都在代码里了。

代码实现

#include

using namespace std;

#define MAX_NUM 8 //皇后数量

int queen[MAX_NUM][MAX_NUM] = { 0 };

bool check(int x, int y) { //检查一个坐标是否可以放置

for (int i = 0; i < y; i++) {

if (queen[x][i] == 1) { //这一行是否可以存在

return false;

}

if (x - 1 - i > 0 && queen[x - 1 - i][y - 1 - i] == 1) { //检查左斜列

return false;

}

if (x + 1 + i < MAX_NUM && queen[x + 1 + i][y + 1 + i] == 1) { //检查右斜列

return false;

}

}

queen[x][y] = 1;

return true;

}

void showQueen() {

for (int i = 0; i < MAX_NUM; i++) {

for (int j = 0; j < MAX_NUM; j++) {

cout << queen[i][j] << " ";

}

cout << endl;

}

cout << endl;

}

bool settleQueen(int x) {

if (x == MAX_NUM) { //遍历完毕，找到答案

return true;

}

for (int i = 0; i < MAX_NUM; i++) {

for (int y = 0; y < MAX_NUM; y++) {

queen[y][x] = 0; //清空当前列，省的回溯的时候被打扰

}

if (check(i,x)) { //如果这行找着了

queen[i][x] = 1;

showQueen(); //直观测试结果

if (settleQueen(x + 1)) { //是时候往左了

return true; //一路往左

}

}

}

return false; //如果不行，就退回来

}

---

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3

输出：[

“((()))”,

“(()())”,

“(())()”,

“()(())”,

“()()()”

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/generate-parentheses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

代码实现

vector generateParenthesis(int n) {

vector res;

generateParenthesisDFS(n, n, “”, res);

return res;

}

void generateParenthesisDFS(int left, int right, string out, vector &res) {

if (left > right) return;

if (left == 0 && right == 0) res.push_back(out);

else {

if (left > 0) generateParenthesisDFS(left - 1, right, out + ‘(’, res);

if (right > 0) generateParenthesisDFS(left, right - 1, out + ‘)’, res);

}

}

---

全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

怎么用，是不是感觉千头万绪，但是又捋不出一个头绪来，很难受。

思路

“全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N! 这么多个。

大家可以尝试一下在纸上写 3 个数字、4 个数字、5 个数字的全排列，相信不难找到这样的方法。

以数组 [1, 2, 3] 的全排列为例。

我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]；

再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]；

最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]。

我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。

在枚举第一位的时候，有 3 种情况。

在枚举第二位的时候，前面已经出现过的数字就不能再被选取了；

在枚举第三位的时候，前面 2 个已经选择过的数字就不能再被选取了。

使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。

说明：

1、每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现；

2、这些变量的不同的值，也称之为“状态”；

3、使用深度优先遍历有“回头”的过程，在“回头”以后，状态变量需要设置成为和先前一样；

4、因此在回到上一层结点的过程中，需要撤销上一次选择，这个操作也称之为“状态重置”；

5、深度优先遍历，可以直接借助系统栈空间，为我们保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈。

6、深度优先遍历通过“回溯”操作，实现了全局使用一份状态变量的效果。

下面我们解释如何编码：

1、首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即在已经选了一些数的前提，我们需要在剩下还没有选择的数中按照顺序依次选择一个数，这显然是一个递归结构；

2、递归的终止条件是，数已经选够了，因此我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth；

3、这些结点实际上表示了搜索（查找）全排列问题的不同阶段，为了区分这些不同阶段，我们就需要一些变量来记录为了得到一个全排列，程序进行到哪一步了，在这里我们需要两个变量：

（1）已经选了哪些数，到叶子结点时候，这些已经选择的数就构成了一个全排列；

（2）一个布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1) 的时间复杂度判断这个数是否被选择过，这是一种“以空间换时间”的思想。

我们把这两个变量称之为“状态变量”，它们表示了我们在求解一个问题的时候所处的阶段。

4、在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。

5、另外，因为是执行深度优先遍历，从较深层的结点返回到较浅层结点的时候，需要做“状态重置”，即“回到过去”、“恢复现场”，我们举一个例子。

从 [1, 2, 3] 到 [1, 3, 2] ，深度优先遍历是这样做的，从 [1, 2, 3] 回到 [1, 2] 的时候，需要撤销刚刚已经选择的数 3，因为在这一层只有一个数 3 我们已经尝试过了，因此程序回到上一层，需要撤销对 2 的选择，好让后面的程序知道，选择 3 了以后还能够选择 2。

这种在遍历的过程中，从深层结点回到浅层结点的过程中所做的操作就叫“回溯”。

作者：liweiwei1419

链接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

代码实现

vector<vector> permute(vector& nums) {

if(nums.empty()) return {};

// 存放最后结果

vector<vector> ans;

// 存放某一个排列

vector temp;

// 判断该数字是否被使用过

vector used(nums.size(),false);

// 进行递归求解

dfs(ans,temp,used,nums);

return ans;

}

void dfs(vector<vector>& ans,vector& temp,vector& used,

const vector& nums)

{

// 如果当前排列数组的长度等于输入数组的长度

// 该排列已完成

// 将该排列的加入结果中，返回

if(temp.size()==nums.size())

{

ans.push_back(temp);

return;

}

// 循环的进行枚举所有状态

for(int i=0;i<nums.size();++i)

{

// 该数字已经选择过，跳过

if(used.at(i)) continue;

// 选择当前数字

temp.push_back(nums.at(i));

// 记录该数字已被选择

used.at(i)=true;

// 递归选择下一个数字

dfs(ans,temp,used,nums);

// 回溯，撤销当前选择

used.at(i)=false;

temp.pop_back();

}

}

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）

最后

由于细节内容实在太多了，为了不影响文章的观赏性，只截出了一部分知识点大致的介绍一下，每个小节点里面都有更细化的内容！

小编准备了一份Java进阶学习路线图（Xmind）以及来年金三银四必备的一份《Java面试必备指南》

《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
ck();

}

}

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。[外链图片转存中…(img-9SeHDnxI-1713522447192)]

[外链图片转存中…(img-eTPHmpsp-1713522447196)]

[外链图片转存中…(img-ElXFJemn-1713522447198)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）

最后

由于细节内容实在太多了，为了不影响文章的观赏性，只截出了一部分知识点大致的介绍一下，每个小节点里面都有更细化的内容！

[外链图片转存中…(img-tdAbZJ9y-1713522447199)]

小编准备了一份Java进阶学习路线图（Xmind）以及来年金三银四必备的一份《Java面试必备指南》

[外链图片转存中…(img-B3IhivQk-1713522447201)]

《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！