算法刷题Day 24 回溯算法理论基础+组合-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法刷题Day 24 回溯算法理论基础+组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Day 24 回溯算法

理论基础

回溯法，一般可以解决如下几种问题：

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

回溯算法模板框架如下：

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

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

组合

class Solution {
    vector<vector<int>> table;
    vector<int> path;

    void backtracking(int start, int end, int k)
    {
        if (path.size() == k)
        {
            table.push_back(path);
            return;
        }

        for (int i = start; i <= end; ++i)
        {
            path.push_back(i);
            backtracking(i + 1, end, k);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        table.clear();
        path.clear();

        backtracking(1, n, k);
        return table;
    }
};

剪枝

回溯的剪枝是面试有可能被问到的点文章来源地址https://www.toymoban.com/news/detail-613979.html

class Solution {
    vector<vector<int>> table;
    vector<int> path;

    void backtracking(int start, int end, int k)
    {
        if (path.size() == k)
        {
            table.push_back(path);
            return;
        }

        for (int i = start; i <= end - (k - path.size()) + 1; ++i)
        {
            path.push_back(i);
            backtracking(i + 1, end, k);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        table.clear();
        path.clear();

        backtracking(1, n, k);
        return table;
    }
};