《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合

《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合

本篇文章的所有内容仅基于C++撰写。

1. 基础知识

1.1 概念

回溯是递归的副产品,它也是遍历树的一种方式,其本质是穷举。它并不高效,但是比暴力循环要快得多,在一些没有更高效解法的题目中,回溯是很好的方法。例如以下题目:

  • 组合问题:N个数里面按一定规则找出k个数的集合(组合不强调元素顺序,排列强调元素顺序。)
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

所有的回溯法都可以抽象为树形结构,因为回溯法解决的都是在集合中递归查找子集,所以集合的大小就构成了树的宽度,递归的深度就构成了树的深度。递归有终止条件,所以必然是一棵高度有限的树(N叉树)。

1.2 模板

  1. 回溯函数的返回值与参数
    回溯算法中函数返回值一般为void,但参数需要根据具体题目确定。
  2. 回溯函数的终止条件
    一般搜索到叶子节点就找到了答案,可以结束本次递归。
  3. 回溯函数的遍历过程
    回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度。
    在这里插入图片描述
  4. 代码
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

2. 组合

2.1 题目

组合

给定两个整数 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

2.2 分析

这道题中的n和k值如果很大,使用for循环嵌套将会造成维数灾难。此时回溯法就发挥了很好的作用。我们使用for循环在当前集合内选一个数作为节点,再使用递归法进入下一层(以当前节点值之后的所有元素形成新的集合),然后再使用for循环选数,重复此操作,直到一条树枝上的节点数量达到目标值k。
其中,回溯操作就是在一个树枝上push_back后再进行pop_back的操作,以确保for能在同一个树层上遍历。
注意有个startindex,这个值用来确定for循环从哪个值开始遍历并进入递归

2.3 代码

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;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

3. 组合III

3.1 题目

组合III

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。

提示:
2 <= k <= 9
1 <= n <= 60

3.2 分析

节点累加找到相加值为n的树枝时,说明找到了一条正确的数枝。因此,这道题相对于上一题只是变更了终止条件中的结果记录方式,如果元素个数达到目标值k时,需要判断当前总值是否与目标值相等:相等则将树枝加入结果集再返回,不相等则直接return。同样会使用startindex。
另外这道题会涉及到剪枝操作:如果当前值已经大于了目标值,那么就不需要再继续遍历了。此外,for循环的范围也可以剪枝:i <= 9 - (k - path.size()) + 1,其中:

  • 已经选择的元素个数:path.size();
  • 所需需要的元素个数为: k - path.size();
  • 列表中剩余元素(n-i) >= 所需需要的元素个数(k - path.size())
  • 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1,开始遍历

这个剪枝方式是横向的,因为在该类题的场景下,for循环在同层越往后遍历,集合越小,以至于节点数量可能小于了目标值k,这时候就不需要再遍历了,这些树枝就可以被剪掉。

3.3 代码

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;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

4. 电话号码的字母组合

4.1 题目

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2:
输入:digits = “”
输出:[]

示例 3:
输入:digits = “2”
输出:[“a”,“b”,“c”]

提示:
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

4.2 分析

这里的集合不再是数字,因此需要考虑映射问题,可以使用map或定义一个二维数组来完成映射。其原理与上两题类似,只是其中的startindex变为了index,其内涵也不相同。index要在给出的数字用例中遍历,例如“233”或“4567”。因此终止条件就是遍历完这些数字用例。另外注意考虑边界条件。

4.3 代码

// 版本一
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;
    }
};
  • 时间复杂度: O(3^m * 4^n),其中 m 是对应三个字母的数字个数,n 是对应四个字母的数字个数
  • 空间复杂度: O(3^m * 4^n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/967059.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Qt监控设备离线检测/实时监测设备上下线/显示不同的状态图标/海康大华宇视华为监控系统

一、前言说明 监控系统中一般有很多设备&#xff0c;有些用户希望知道每个设备是否已经上线&#xff0c;最好有不同的状态图标提示&#xff0c;海康的做法是对设备节点的图标和颜色变暗处理&#xff0c;离线的话就变暗&#xff0c;有可能是加了透明度&#xff0c;而大华的处理…

初次体验Tauri和Sycamore (2)

原创作者&#xff1a;庄晓立&#xff08;LIIGO&#xff09; 原创时间&#xff1a;2025年2月8日&#xff08;首次发布时间&#xff09; 原创链接&#xff1a;https://blog.csdn.net/liigo/article/details/145520637 版权所有&#xff0c;转载请注明出处。 关键词&#xff1a;Sy…

模型压缩 --学习记录2

模型压缩 --学习记录2 如何找到更好的权衡方式(模型量化)方法一:寻找更好的 range方法二:寻找更好的 X-fp32(浮点数)方法三:寻找更好的 scale 和 zp方法四:寻找更好的 roundPTQ 后训练量化(离线量化)QAT 量化感知训练(在线量化)量化为什么会带来加速?三、模型稀疏技…

Vue与Konva:解锁Canvas绘图的无限可能

前言 在现代Web开发中&#xff0c;动态、交互式的图形界面已成为提升用户体验的关键要素。Vue.js&#xff0c;作为一款轻量级且高效的前端框架&#xff0c;凭借其响应式数据绑定和组件化开发模式&#xff0c;赢得了众多开发者的青睐。而当Vue.js邂逅Konva.js&#xff0c;两者结…

8.JVM-方法区

前言 这次所讲述的是运行时数据区的最后一个部分 从线程共享与否的角度来看 ThreadLocal&#xff1a;如何保证多个线程在并发环境下的安全性&#xff1f;典型应用就是数据库连接管理&#xff0c;以及会话管理 栈、堆、方法区的交互关系 下面就涉及了对象的访问定位 Person&a…

面向对象程序设计-实验3

题目1 &#xff08;给出题目描述&#xff09;设计一个类CRectangle 代码清单&#xff1a; #include<iostream> using namespace std; class CRectangle { public: CRectangle() { m_l1.0; m_w1.0; } void get() { cin>>m_l; if(m_l>50) { m_l1.0; } cin&g…

边缘计算网关驱动智慧煤矿智能升级——实时预警、低延时决策与数字孪生护航矿山安全高效运营

迈向智能化煤矿管理新时代 工业物联网和边缘计算技术的迅猛发展&#xff0c;煤矿安全生产与高效运营正迎来全新变革。传统煤矿监控模式由于现场环境复杂、数据采集和传输延时较高&#xff0c;已难以满足当下高标准的安全管理要求。为此&#xff0c;借助边缘计算网关的实时数据…

deepseek本地部署+web图形化页面配置+对比其他ai模型

公众号&#xff1a;泷羽Sec-尘宇安全 前言 最近deepseek非常火&#xff0c;训练成本低&#xff0c;其预训练费用仅为OpenAI GPT-4o模型的不到十分之一&#xff0c;但是效果堪比OpenAI&#xff0c;使用深度思考&#xff0c;回答的问题很不错&#xff0c;啥都敢说 可惜惨遭ddos…

Deepseek 接入Word处理对话框(隐藏密钥)

硅基流动邀请码&#xff1a;1zNe93Cp 邀请链接&#xff1a;网页链接 亲测deepseek接入word&#xff0c;自由调用对话&#xff0c;看截图有兴趣的复用代码&#xff08;当然也可以自己向deepseek提问&#xff0c;帮助你完成接入&#xff0c;但是提问逻辑不一样给出的答案是千差万…

从家庭IP到全球网络资源的无缝连接:Cliproxy的专业解决方案

数字化时代&#xff0c;家庭IP作为个人或家庭接入互联网的门户&#xff0c;其重要性日益凸显。然而&#xff0c;要实现从家庭IP到全球网络资源的无缝连接&#xff0c;并享受高效、安全、稳定的网络访问体验&#xff0c;往往需要借助专业的代理服务。Cliproxy&#xff0c;作为业…

微信点餐系统小程序ssm+论文源码调试讲解

第4章 系统设计 一个成功设计的系统在内容上必定是丰富的&#xff0c;在系统外观或系统功能上必定是对用户友好的。所以为了提升系统的价值&#xff0c;吸引更多的访问者访问系统&#xff0c;以及让来访用户可以花费更多时间停留在系统上&#xff0c;则表明该系统设计得比较专…

牛客寒假集训营2

A 牛客传送门 代码如下: const int N2e610,M1e410; const int INF0x3f3f3f3f; const int mod998244353; ll n;void solve(){map<int,int>mp;mp[1]mp[2]mp[3]mp[5]mp[6]1;for(int i1;i<7;i){int a…

第3章 使用 Vue 脚手架

第3章 使用 Vue 脚手架 3.1 初始化脚手架3.1.1 说明3.1.2. 具体步骤3.1.3 分析脚手架结构1 总结2 细节分析1 配置文件2 src文件1 文件结构分析2 例子 3 public文件4 最终效果 3.2 ref属性3.3 props配置项3.4 mixin混入3.5 插件3.6 scoped样式3.7 Todo-list 案例3.7.1 组件化编码…

去除install4j学习版生成的安装程序和主程序的neg弹窗的解决思路

文章目录 去除install4j学习版生成的安装程序和主程序的neg弹窗的解决思路概述笔记打补丁之前打补丁之后 效果备注 END 去除install4j学习版生成的安装程序和主程序的neg弹窗的解决思路 概述 最近可能有修改openpnp源码并打包的需求。 openpnp2.2 用 install4j 10.0.5 来打包…

前后端服务配置

1、安装虚拟机&#xff08;VirtualBox或者vmware&#xff09;&#xff0c;在虚拟机上配置centos(选择你需要的Linux版本)&#xff0c;配置如nginx服务器等 1.1 VMware 下载路径Sign In注册下载 1.2 VirtualBox 下载路径https://www.virtualbox.org/wiki/Downloads 2、配置服…

基于javaweb的SpringBoot+MyBatis毕业设计选题答辩管理系统(源码+文档+部署讲解)

&#x1f3ac; 秋野酱&#xff1a;《个人主页》 &#x1f525; 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 运行环境开发工具技术框架适用功能说明eclipse/MyEclipse运行&#xff1a; ![在这里插入图片描述](https://i-blog.csdnimg.cn/dir…

【Elasticsearch】nested聚合

在 Elasticsearch 中&#xff0c;嵌套聚合&#xff08;nestedaggregation&#xff09;的语法形式用于对嵌套字段&#xff08;nestedfields&#xff09;进行聚合操作。嵌套字段是 Elasticsearch 中的一种特殊字段类型&#xff0c;用于存储数组中的对象&#xff0c;这些对象需要独…

Linux第106步_Linux内核RTC驱动实验

1、了解rtc_device结构体 1)、打开“include/linux/rtc.h” rtc_class_ops是需要用户根据所使用的RTC设备编写的,其结构体如下: struct rtc_class_ops { int (*ioctl)(struct device *, unsigned int, unsigned long);/*函数指针ioctl*/ int (*read_time)(struct device *,…

微信小程序案例2——天气微信小程序(学会绑定数据)

文章目录 一、项目步骤1 创建一个weather项目2 进入index.wxml、index.js、index.wxss文件,清空所有内容,进入App.json,修改导航栏标题为“中国天气网”。3进入index.wxml,进行当天天气情况的界面布局,包括温度、最低温、最高温、天气情况、城市、星期、风行情况,代码如下…

Linux系统-centos防火墙firewalld详解

Linux系统-centos7.6 防火墙firewalld详解 1 firewalld了解 CentOS 7.6默认的防火墙管理工具是firewalld&#xff0c;它取代了之前的iptables防火墙。firewalld属于典型的包过滤防火墙或称之为网络层防火墙&#xff0c;与iptables一样&#xff0c;都是用来管理防火墙的工具&a…