当前位置： 首页 > article >正文

DAY22|回溯算法Part01|LeetCode: 77. 组合、216.组合总和III 、17.电话号码的字母组合

article 2024/11/9 6:11:49

目录

回溯算法

算法流程

回溯算法代码模版

LeetCode: 77. 组合

基本思路

C++代码

LeetCode: 216.组合总和III

基本思路

C++代码

LeetCode: 17.电话号码的字母组合

基本思路

C++代码

回溯算法

算法流程

        做题之前，首先要先了解什么是回溯算法以及为什么要使用回溯算法？

        回溯法也可以叫做回溯搜索法，它是一种搜索的方式。在前面做递归的题目之前，我们就已经提到过回溯相关的知识，实际上回溯是递归的副产品，只要有递归就会有回溯。所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。而回溯算法通常用来解决组合、分割、子集、排列以及棋盘问题等方面的问题。

        在之前的递归方法中提出了递归三部曲，同样的我们在回溯算法中也同样可以归纳为回溯三部曲：

  • 回溯函数模板返回值以及参数

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

void backtracking(参数)
  • 回溯函数终止条件

        由于同样可以将问题抽象为树形结构，因此在遍历时就一定会存在终止条件，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

if (终止条件) {
    存放结果;
    return;
}
  • 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

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

        大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

回溯算法代码模版

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

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

LeetCode: 77. 组合

力扣代码链接

文字讲解：LeetCode: 77. 组合

视频讲解：带你学透回溯算法-组合问题

基本思路

        对于这种类似的题目，如果k=2，最容易想到的就是使用两层for循环来得到所有可能的集合。但是如果k远大于2，等于50，等于100会怎么样？50层for循环或是100层for循环？绝对可以让人窒息，所以需要抽象图形结构来进一步理解。

使用回溯法，回溯三部曲：

定义一个一维数组用来记录符合条件的结果，再定义一个二维数组用来记录结果集。

  • 确定递归函数参数和返回值

        参数：传入n和k，还需要传入一个int类型的变量startIndex，用来记录for循环遍历的位置。

        返回值：返回值一般都是void。

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

        path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了。此时用result二维数组，把path保存起来，并终止本层递归。

if (path.size() == k) {
    result.push_back(path);
    return;
}
  • 单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

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

C++代码

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;
    }
};

//通过剪枝进行优化
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 - (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 result;
    }
};

LeetCode: 216.组合总和III

力扣代码链接

文字讲解：LeetCode: 216.组合总和III

视频讲解：和组合问题有啥区别？回溯算法如何剪枝？

基本思路

依旧要视为树形结构，树的宽度由我们的集合长度决定[ 1 , 9 ] [1, 9][1,9]，树的深度由k来决定。

        依然定义path 和 result为全局变量。

  • 确定递归函数参数

        参数：定义目标和targetSum（int类型）（即题目中的n），定义k，定义已经收集的元素的总和sum，也就是path里元素的总和，定义下一层for循环搜索的起始位置startIndex。

        返回值：为void。

vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex)
  • 确定终止条件

        所以如果path.size() 和 k相等了，就终止。

if (path.size() == k) {
    if (sum == targetSum) result.push_back(path);
    return; // 如果path.size() == k 但sum != targetSum 直接返回
}
  • 单层搜索过程

处理过程就是 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。

for (int i = startIndex; i <= 9; i++) {
    sum += i;
    path.push_back(i);
    backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
    sum -= i; // 回溯
    path.pop_back(); // 回溯
}
  • 剪枝

        已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。同样for循环的范围也可以剪枝，i <= 9 - (k - path.size()) + 1就可以了。

C++代码

class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果
    void backtracking(int targetSum, int k, int sum, int startIndex) {
        if (sum > targetSum) { // 剪枝操作
            return; 
        }
        if (path.size() == k) {
            if (sum == targetSum) result.push_back(path);
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
            sum += i; // 处理
            path.push_back(i); // 处理
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
            sum -= i; // 回溯
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不加
        path.clear();   // 可以不加
        backtracking(n, k, 0, 1);
        return result;
    }
};

LeetCode: 17.电话号码的字母组合

力扣代码链接

文字讲解：LeetCode: 17.电话号码的字母组合

视频讲解：还得用回溯算法！

基本思路

        首先我们应该建立一个map映射，将数字和字母相对应。这里我们可以使用二维数组。

const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};

        其次，第一次做这种题目还是很难构思出树的结构，下面直接给出：

        树的深度是由我们输入的数字个数来定，树的宽度就是数字所对应的字母的长度来控制。

        首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来。

  • 确定回溯函数参数和返回值

        参数：题目中给的string digits，然后还要有一个参数就是int型的index，这里的Index不是前面的startIndex，这里的两个字符串不属于同一个数组，用来记录遍历到第几个字符。

        返回值：一般为void类型。

vector<string> result;
string s;
void backtracking(const string& digits, int index)
  • 确定终止条件

        如果index 等于 输入的数字个数表明已经遍历完成当前字符串中的所有字符，即终止。

if (index == digits.size()) {
    result.push_back(s);
    return;
}
  • 确定单层遍历逻辑

        首先要取index指向的数字，并找到对应的字符集(为char类型，因此可以使用对应的ASCII码减去0的ASCII码，将其转换为int类型)，然后for循环来处理这个字符集。

int digit = digits[index] - '0';        // 将index指向的数字转为int
string letters = letterMap[digit];      // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
    s.push_back(letters[i]);            // 处理
    backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了
    s.pop_back();                       // 回溯
}

C++代码

// 版本一
class Solution {
private:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result;
    string s;
    void backtracking(const string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';        // 将index指向的数字转为int
        string letters = letterMap[digit];      // 取数字对应的字符集
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);            // 处理
            backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了
            s.pop_back();                       // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

http://www.kler.cn/a/385432.html

相关文章：

  • JavaScript 实现文本转语音功能
  • LVGL 与 QT
  • 使用containerd搭建kubernetes集群
  • 深度学习：自注意力机制（Self-attention）详解
  • Vue2 doc、excel、pdf、ppt、txt、图片以及视频等在线预览
  • 美格智能5G车规级通信模组：高精度定位守护极致安全
  • 2024年入职_转行网络安全，该如何规划？
  • OJ06：206.反转链表
  • 保障性住房管理：SpringBoot技术优势分析
  • 化工厂主要涉及的自动化备件有哪些？
  • go语言中package详解
  • MySQL 8.0中的‘caching_sha2_password‘身份验证插件问题
  • Gemini 对话机器人加入开源盲水印技术来检测 AI 生成的内容
  • Scala包对象。
  • java导出word文件(手绘)
  • GCC和clang的爱恨情仇
  • 【Linux系统】—— 基本指令（二）
  • SpringBoot实现的企业资产管理系统
  • 纯C++信号槽使用Demo （sigslot 库使用）
  • PyQt入门指南四十六 性能优化策略
  • AntPathMatcher 技术文档
  • Affinity part 2 - 系统拓扑结构和控制亲和性
  • 气膜场馆：推动体育文化旅游创新发展的关键力量—轻空间
  • 支付宝与华为终端联手，移动支付即将进入“碰时代”
  • 掌握springboot过滤器,拦截器 ,aop
  • 宠物空气净化器哪家好？希喂、安德迈、霍尼韦尔除毛能力测评