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

输出两位以内的数

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