C++回溯

CSDN 2024-10-05 12:35:02 阅读 91

我对回溯的定义是不定层循环,此定义并不规范,但容易理解。回溯基本上用深度优先搜索实现,暂未发现反例。而深度优先搜索绝大部分是用递归实现。

输出两位以内的数

注意:1位数,也要输出,前面补0。代码很简单,两层循环:分别枚举十位数和个位数。

<code>int main()

{ -- -->

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

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

std::cout << i << j << " ";

}

}

}

输出 n位以内的3进制数

低于n位的数,也要输出。不足n位的,前面补0到n位。

#include <iostream>

#include <functional>

#include <vector>

using namespace std;

int main()

{

int n = 0;

std::cout << "请输入n\r\n";

std::cin >> n;

vector<int> path;

std::function<void()> BackTrack = [&]() {

if (path.size() == n) {

for (auto& tmp : path) {

std::cout << tmp;

}

std::cout << " ";

return;

}

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

path.emplace_back(i);

BackTrack();

path.pop_back();

}

};

BackTrack();

}

本题扩展:

一,输出m进制。

二,0,00,000分别输出。如:n=2 m=2,包括{0,1,00,01,10,11}

回溯总结

五点:

一,路径(状态),已经做出的选择。恢复状态主要针对它。

二,结束条件。

三,需要处理的路径。

四,子回溯,从选择列表中做出选择。

五,初始调用。

有些场景,在”结束条件“之前,还需要剪枝,去掉非法和被淘汰的分支。

在这里插入图片描述

时间复杂度:O(选择列表的长度层次) ,由于有大量剪枝,实际复杂度少得多。

教科书定义

回溯算法,又称为“试探法”。解决问题时,每进行一步,都是抱着试试看的态度,如果发现当前选择并不是最好的,或者这么走下去肯定达不到目标,立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯算法。

解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:

1、路径:也就是已经做出的选择。

2、选择列表:也就是你当前可以做的选择。

3、结束条件:也就是到达决策树底层,无法再做选择的条件。

题解

回溯状态只需要知道路径层次 难度分
【回溯 状态压缩 枚举】2151. 基于陈述统计最多好人数 1797
【回溯】1255. 得分最高的单词集合 1881
【状态压缩 枚举 回溯】1601. 最多可达成的换楼请求数目 2118
【回溯 栈 代数系统 动态规划】282. 给表达式添加运算符
回溯状态需要栈 难度分
【图论 回溯 广度优先搜索】126. 单词接龙 II
【回溯 图论】2065. 最大化一张图中的路径价值 2178
难度分
【回溯 深度优先搜索】980. 不同路径 III 1830
【回溯】1240. 铺瓷砖 2241
【性能优化】 【回溯】 【字符串】1307. 口算难题 2250
【回溯 字典树(前缀树)】212. 单词搜索 II
【回溯 代数系统】679. 24 点游戏
LeetCode37. 解数独
【回溯 网格 状态压缩】52. N 皇后 II

LeetCode暂无题解

140 301 691 996

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法用**C++**实现。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。