代码随想录算法训练营第二十四天 | 第七章 回溯算法-理论基础，77. 组合

一、参考资料

理论基础

题目链接/文章讲解：https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

视频讲解：https://www.bilibili.com/video/BV1cy4y167mM

组合

题目链接/文章讲解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

视频讲解：https://www.bilibili.com/video/BV1ti4y1L7cv

剪枝操作：https://www.bilibili.com/video/BV1wi4y157er

二、理论基础

回溯的遍历过程如图：

三、LeetCode77. 组合

https://leetcode.cn/problems/combinations/description/

组合问题抽象

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]

提示：
1 <= n <= 20
1 <= k <= n

class Solution {
private:
    vector<vector<int>> res;  // 定义一个结果集数组
    vector<int> path;  // 定义路径，用来存放符合条件的结果

    void backtracking (int n, int k, int startIndex) {
        if (path.size() == k) {
            res.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) {
        backtracking(n, k, 1);
        return res;
    }
};

我写的：

class Solution {
private:
    vector<int> path;   // 用于存放符合条件的路径
    vector<vector<int>> res;    // 用于存放结果集

    void backtracking(int n, int k, int startIndex) {
        // startIndex是为了防止重复组合（排列才和元素顺序有关）
        if (path.size() == k) {
            res.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) {
        backtracking(n, k, 1);
        return res;
    }
};

剪枝操作：【看了两三遍，这个剪枝的条件有点点绕的】

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

注意代码中i，就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) {

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 还需要的元素个数为: k - path.size();

3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

class Solution {
// 剪枝
private:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            res.push_back(path);
            return ;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
};

今日总结：

有新的任务了，往后刷题可真就是海绵里挤水，时间变得更加宝贵==

学到兴致处时常感慨，时间过得太快了，想学的都学不完。

关于回溯：

在二叉树的基础上，理解还行，就是剪枝的条件有一点点没懂，看讲解能明白，自己想不一定写出来

另外在组合问题上，需要注意它不需要考虑元素的顺序，所以代码中startIndex的出现，就是标记N叉树下一层所需要选择的起始位置，每次都在前一层的基础上加1。