算法刷题Day24 | 回溯算法基础理论、 77. 组合

0 引言

没错，忙完腾讯面试，我胡汉三又回来了，哈哈，加油

1 回溯算法基础理论

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

1.1 回溯算法模板

在递归中有三部曲：

递归函数的参数和返回值
递归函数终止的条件
单层递归的逻辑

回溯三部曲：

回溯函数返回值和参数：函数名一般为 backtracking，返回值一般为 void。再来看一下参数，回溯算法的参数不像二叉树递归你们容易一次性确定下来，所以一般先写逻辑，然后需要什么参数就填什么参数。
回溯函数的终止条件：判断是否满足终止条件，满足的话先将结果保存，然后再 return。
单层回溯的逻辑：选择、递归、撤回选择

代码模板如下：

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

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

1.2

2 组合

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

组合和排列的区别，组合的话 {1，2} 和 {2，1} 是同样的结果，但是在排列中就是两种结果。

2.1 我的解题

有了之前递归的基础，再来写回溯就觉得还是可以理解的。回溯算法中的单层回溯往往涉及一个for循环，因为我们是将回溯问题转换成了一个n叉树来解决，所以要遍历当前层数的所有分支。而在之前二叉树的题目中，因为树的分支就两个，所以在单层递归逻辑中直接就是分别调用左右子树进行两次递归就行。

class Solution {
public:
    // 1. 参数和返回值
    void backTracing(int& n, int& k, int startIndex, vector<int>& path, vector<vector<int>>& res)
    {
        // 2. 递归终止条件
        if (path.size() == k)
        {
            res.push_back(path);
            return;
        }

        // 3. 单层回溯逻辑
        for (int i = startIndex; i <= n; i++)
        {
            path.push_back(i);
            backTracing(n, k, i+1, path, res);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        backTracing(n, k, 1, path, res);
        return res;
    }
};

2.2 剪枝操作

剪枝的原理：我们要搜索一个大小为n的集合结果，但是此时剩余需要判断的元素已经不足n了。就拿刚才的代码距离，当n为4，k也为4的时候。假如此时的 startIndex为 2，当前 path 的元素个数为 1 。就代表这个分支怎么组合都不可以会出现path元素个数等于4的情况。此时这个分支就可以去除了。

在这里插入图片描述

代码如下：只修改了单层回溯逻辑的代码，增加了一个剪枝的操作。

        // 3. 单层回溯逻辑
        // 先进行剪枝
        int maxCount = n - startIndex + 1 + path.size();
        if (maxCount < k)
        {
            return;
        }

        for (int i = startIndex; i <= n; i++)
        {
            path.push_back(i);
            backTracing(n, k, i+1, path, res);
            path.pop_back();
        }