代码随想录算法训练营第24天 | 回溯法理论基础, 77.组合

回溯法理论基础

代码随想录链接

什么是回溯

回溯是一种搜索的方式, 其本质是穷举, 是递归的副产品, 只要有递归就会有回溯.

回溯法难理解, 但并不高校, 因为其本质是穷举所有可能, 然后筛选出符合要求的答案, 最多只能通过剪枝来减少穷举的部分, 但不能改变其本质.

回溯能解决的问题

• 组合问题
  • N个数里找出k个数的集合(无序)
• 切割问题
  • 一个字符串按照一定的规则有几种切割方式
• 子集问题
  • N个数找出K个熟的排列(有序)
• 排列问题
  • N个数按照一定的规则的全排列
• 棋盘问题
  • N皇后, 解数独等

理解回溯法

回溯法解决的问题都可以抽象为树型结构, 集合的大小就是熟的宽度, 递归的深度, 就是熟的深度.

递归需要有终止条件, 所以这棵递归树一定是一棵高度有限的树.

回溯法模板

回溯三部曲:

回溯法函数模板返回值及参数

回溯算法中函数返回值一般为void, 参数需要在写逻辑时确定需要什么参数

void backtracing(DataType param)

回溯函数终止条件

在回溯树中的叶子节点时的处理逻辑, 搜到叶子结点, 也就找到了满足条件的一条答案, 把这个答案存放起来, 并结束本层递归.

if (endCondition) {
    /**
     *  Store the result;
     */
     return;
}

回溯遍历过程

回溯法遍历过程

for循环横向遍历, 递归进行纵向遍历

for (DataType child : thisLayer) {
    processThisNode();
    backtracing(Path, Selection); // Recursion
    back(); // 回溯，撤销处理结果
}

综上可以得出回溯法模板框架如下:

void backtracing(type<A> param) {
    if (endCondition) {
    /**
     *  Store the result;
     */
     return;
    }

    for (DataType child : thisLayer) {
        processThisNode();
        backtracing(Path, Selection); // Recursion
        back(); // 回溯，撤销处理结果
    }
}

77.组合

代码随想录链接

题目

LeetCode-77.组合

给定两个整数 n 和 k, 返回在[1, n]范围中的所有的 K 个数的集合.

自己的想法

暴力法第24天了哥, 别暴力了

上面不是才学了回溯的理论基础吗, 这道题肯定要拿回溯来做, 回溯的层序遍历可以是找剩下的数中组合开头的数, 然后递归地往结果内加下一个k-1个数的组合.

由于求的是组合, 所以在找k-1个数的组合的时候, 就一定要指明找的边界, 不能把找过的数再次放入.

解法

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(int n, int k, int startIndex) {    // 回溯递归
        if (path.size() == k) {                         // 集合中满足了k个数, 则记录结果, 结束递归
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {         // 横向遍历
            path.push_back(i);                          // 推入这个数
            backtracing(n, k, i + 1);                   // 纵向递归, 回溯法
            path.pop_back();                            // 完成了当前这个数的组合的查找, 取出这个数
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtracing(n, k, 1);
        return this -> result;
    }
};

上面的代码仍然存在一些不必要的步骤, 进行for循环时, 如果i右侧的数不足以填满集合内剩下的空位, 那么就没有必要继续for循环下去, 据此可以进行剪枝操作:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size() - 1); i++) { // 新增了判断是否还有足够的数来填充集合空位
            path.push_back(i);
            backtracing(n, k, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtracing(n, k, 1);
        return this -> result;
    }
};