C++回溯

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

输出两位以内的数

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

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、结束条件：也就是到达决策树底层，无法再做选择的条件。

题解

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++**实现。