1. 回溯算法理论基础

代码随想录： 原文

1.1 什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式
回溯是递归的副产品，只要有递归就会有回溯

1.2 回溯法的效率

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案
想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质

1.3 回溯法解决的问题

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

注意：组合是不强调元素顺序的，排列是强调元素顺序，组合无序，排列有序

1.4 如何理解回溯法

回溯法解决的问题都可以抽象为树形结构
回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度构成的树的深度
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）

1.5 回溯法模板

回溯三部曲

1. 回溯函数模板返回值以及参数

函数起名字为backtracking
回溯算法中函数返回值一般为void
回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数

void backtracking(参数)

2. 回溯函数终止条件

一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归

if (终止条件) {
    存放结果;
    return;
}

3. 回溯搜索的遍历过程

回溯法一般是在集合中递归搜索
集合的大小构成了树的宽度
递归的深度构成的树的深度

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了

回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

2. 组合问题

代码随想录： 原文

力扣题目：第77题. 组合

2.1 思路

要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环
回溯法就用递归来解决嵌套层数的问题
递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了

把组合问题抽象为如下树形结构：

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围
n相当于树的宽度，k相当于树的深度
每次搜索到了叶子节点，我们就找到了一个结果

回溯法三部曲

1. 递归函数的返回值以及参数

定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合

vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果

参数：集合n，k个数，int型变量startIndex用来记录本层递归的中，集合从哪里开始遍历
需要startIndex来记录下一层递归，搜索的起始位置

vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex)

2. 回溯函数终止条件

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径
用result二维数组，把path保存起来，并终止本层递归

if (path.size() == k) {
    result.push_back(path);
    return;
}

3. 单层搜索的过程

for循环每次从startIndex开始遍历，然后用path保存取到的节点i
backtracking（递归函数）通过不断调用自己一直往深处遍历，遇到了叶子节点就要返回
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果

for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.push_back(i); // 处理节点
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

2.2 代码实现

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};

补充：

可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了
所以优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

3. 总结

回溯法解决的问题都可以抽象为树形结构
回溯三部曲灵活应用
回溯过程抽象为一棵树形结构，然后可以直观的看出，剪枝究竟是剪的哪里

出差中，一切从简，学习时间：100min

目录CONTENT

代码随想录算法训练营第二十四天 | 回溯算法理论基础；组合问题