【算法】回溯算法专题② ——组合型回溯 + 剪枝 python
目录
- 前置知识
- 进入正题
- 小试牛刀
- 实战演练
- 总结
前置知识
【算法】回溯算法专题① ——子集型回溯 python
进入正题
组合https://leetcode.cn/problems/combinations/submissions/596357179/
给定两个整数 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
思路:
回溯思路(选或不选 / 枚举选哪个)
剪枝(选不满k个就停止递归)
code1:
class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans = []path = []def dfs(i):# 剪枝if n - i + 1 + len(path) < k: returnif len(path) == k:ans.append(path.copy())return# 不选dfs(i + 1)# 选path.append(i)dfs(i + 1)path.pop()dfs(1)return ans
code2:
class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans = []path = []def dfs(i):# 剪枝if n - i + 1 + len(path) < k:returnif len(path) == k:ans.append(path.copy())return# 枚举选哪个 for j in range(i, n + 1):path.append(j)dfs(j + 1)path.pop()dfs(1)return ans
小试牛刀
组合总和Ⅲ https://leetcode.cn/problems/combination-sum-iii/description/
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
1.只使用数字1到9
2.每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
示例 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
思路:
与上题一样的思路
回溯 + 剪枝
题解1:
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:ans = []path = []def dfs(i):# 剪枝if len(path) + 10 - i < k:returnif sum(path) > n:returnif len(path) == k and sum(path) == n:ans.append(path.copy())return# 选path.append(i)dfs(i + 1)path.pop()# 不选dfs(i + 1)dfs(1)return ans
题解2:
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:ans = []path = []def dfs(i):# 剪枝if len(path) + 10 - i < k:returnif sum(path) > n:returnif len(path) == k and sum(path) == n:ans.append(path.copy())return# 枚举选哪个for j in range(i, 10):path.append(j)dfs(j + 1)path.pop()dfs(1)return ans
当然,我们可以在判断和是否为n时进行优化:
在dfs中传入target参数,每选一个数字 j 就把target减去 j
code:
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:ans = []path = []def dfs(i, t):if len(path) + 10 - i < k:returnif t < 0:returnif len(path) == k and t == 0:ans.append(path.copy())returnfor j in range(i, 10):path.append(j)dfs(j + 1, t - j)path.pop()dfs(1, n)return ans
实战演练
括号生成 https://leetcode.cn/problems/generate-parentheses/
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2:
输入:n = 1
输出:[“()”]
提示:
1 <= n <= 8
思路:
将选理解为填左括号, 不选理解为填右括号
题解:
class Solution:def generateParenthesis(self, n: int) -> List[str]:ans = []path = []def dfs(i, left, right):if i == 2 * n:ans.append("".join(path))return# 左括号数量不能超过nif left < n:path.append("(")dfs(i + 1, left + 1, right)path.pop()# 右括号数量不能超过左括号数量if right < left:path.append(")")dfs(i + 1, left, right + 1)path.pop()dfs(0, 0, 0)return ans
总结
剪枝是一种优化技术,用于提前终止那些不可能找到解的搜索路径,从而提高算法效率。
而组合型回溯问题常常与剪枝相结合
END
如果有更多问题或需要进一步的帮助,可以在评论区留言讨论哦!
如果喜欢的话,请给博主点个关注 谢谢
相关文章:
【算法】回溯算法专题② ——组合型回溯 + 剪枝 python
目录 前置知识进入正题小试牛刀实战演练总结 前置知识 【算法】回溯算法专题① ——子集型回溯 python 进入正题 组合https://leetcode.cn/problems/combinations/submissions/596357179/ 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以…...
LeetCode:121.买卖股票的最佳时机1
跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的! 代码随想录 LeetCode:121.买卖股票的最佳时机1 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票…...

pytorch生成对抗网络
人工智能例子汇总:AI常见的算法和例子-CSDN博客 生成对抗网络(GAN,Generative Adversarial Network)是一种深度学习模型,由两个神经网络组成:生成器(Generator)和判别器࿰…...

Visual Studio Code应用本地部署的deepseek
1.打开Visual Studio Code,在插件中搜索continue,安装插件。 2.添加新的大语言模型,我们选择ollama. 3.直接点connect,会链接本地下载好的deepseek模型。 参看上篇文章:deepseek本地部署-CSDN博客 4.输入需求生成可用…...

用 HTML、CSS 和 JavaScript 实现抽奖转盘效果
顺序抽奖 前言 这段代码实现了一个简单的抽奖转盘效果。页面上有一个九宫格布局的抽奖区域,周围八个格子分别放置了不同的奖品名称,中间是一个 “开始抽奖” 的按钮。点击按钮后,抽奖区域的格子会快速滚动,颜色不断变化…...
Skewer v0.2.2安装与使用-生信工具43
01 Skewer 介绍 Skewer(来自于 SourceForge)实现了一种基于位掩码的 k-差异匹配算法,专门用于接头修剪,特别设计用于处理下一代测序(NGS)双端序列。 fastp安装及使用-fastp v0.23.4(bioinfoma…...
C语言:链表排序与插入的实现
好的!以下是一篇关于这段代码的博客文章: 从零开始:链表排序与插入的实现 在数据结构的学习中,链表是一种非常基础且重要的数据结构。今天,我们将通过一个简单的 C 语言程序,来探讨如何实现一个从小到大排序的链表,并在其中插入一个新的节点。这个过程不仅涉及链表的基…...
【Elasticsearch】doc_values 可以用于查询操作
确实,doc values 可以用于查询操作,尽管它们的主要用途是支持排序、聚合和脚本中的字段访问。在某些情况下,Elasticsearch 也会利用 doc values 来执行特定类型的查询。以下是关于 doc values 在查询操作中的使用及其影响的详细解释ÿ…...

深度学习深度解析:从基础到前沿
引言 深度学习作为人工智能的一个重要分支,通过模拟人脑的神经网络结构来进行数据分析和模式识别。它在图像识别、自然语言处理、语音识别等领域取得了显著成果。本文将深入探讨深度学习的基础知识、主要模型架构以及当前的研究热点和发展趋势。 基础概念与数学原理…...

JVM的GC详解
获取GC日志方式大抵有两种 第一种就是设定JVM参数在程序启动时查看,具体的命令参数为: -XX:PrintGCDetails # 打印GC日志 -XX:PrintGCTimeStamps # 打印每一次触发GC时发生的时间第二种则是在服务器上监控:使用jstat查看,如下所示,命令格式为jstat -gc…...

【开源免费】基于Vue和SpringBoot的校园网上店铺系统(附论文)
本文项目编号 T 187 ,文末自助获取源码 \color{red}{T187,文末自助获取源码} T187,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...

测压表压力表计量表针头针尾检测数据集VOC+YOLO格式4862张4类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):4862 标注数量(xml文件个数):4862 标注数量(txt文件个数):4862 …...
Vue 3 30天精进之旅:Day 12 - 异步操作
在现代前端开发中,异步操作是一个非常常见的需求,例如从后端API获取数据、进行文件上传等任务。Vue 3 结合组合式API和Vuex可以方便地处理这些异步操作。今天我们将重点学习如何在Vue应用中进行异步操作,包括以下几个主题: 异步操…...

【网络】3.HTTP(讲解HTTP协议和写HTTP服务)
目录 1 认识URL1.1 URI的格式 2 HTTP协议2.1 请求报文2.2 响应报文 3 模拟HTTP3.1 Socket.hpp3.2 HttpServer.hpp3.2.1 start()3.2.2 ThreadRun()3.2.3 HandlerHttp() 总结 1 认识URL 什么是URI? URI 是 Uniform Resource Identifier的缩写&…...
[paddle] 矩阵相关的指标
行列式 det 行列式定义参考 d e t ( A ) ∑ i 1 , i 2 , ⋯ , i n ( − 1 ) σ ( i 1 , ⋯ , i n ) a 1 , i 1 a 2 , i 2 , ⋯ , a n , i n det(A) \sum_{i_1,i_2,\cdots,i_n } (-1)^{\sigma(i_1,\cdots,i_n)} a_{1,i_1}a_{2,i_2},\cdots, a_{n,i_n} det(A)i1,i2,⋯,in…...

docker部署SpringBoot项目简单流程
一、docker基础命令理解学习 1、常见命令 docker启动之前要关闭防火墙systemctl stop firewalld # 关闭防火墙systemctl disable firewalld # 禁止开机启动防火墙systemctl start docker # 启动docker服务systemctl stop docker # 停止docker服务systemctl restart docker # …...
Python学习——函数参数详解
Python中的函数参数传递机制允许多种灵活的参数类型,可以根据需求灵活配置参数,这使得函数具有更强大的扩展性和适应性。以下是对各类参数类型的详细说明: 1. 定义函数的不同参数类型 1.1 位置参数 定义方式:def func(a, b2) 特…...

Chromium132 编译指南 - Android 篇(一):编译前准备
1. 引言 欢迎来到《Chromium 132 编译指南 - Android 篇》系列的第一部分。本系列指南将引导您逐步完成在 Android 平台上编译 Chromium 132 版本的全过程。Chromium 作为一款由 Google 主导开发的开源浏览器引擎,为众多现代浏览器提供了核心驱动力。而 Android 作…...
.Net / C# 繁体中文 与 简体中文 互相转换, 支持地方特色词汇
版本号 Nuget 搜索 “OpenCCNET”, 注意别找错, 好多库的名字都差不多 支持 “繁,简” 的互相转换, 支持多个地区常用词汇的转换, 还支持 日文的新旧转换. OpenCC 在 .Net 中的实现 https://github.com/CosineG/OpenCC.NET <PackageReference Include"OpenCCNET"…...
Java泛型深度解析(JDK23)
第一章 泛型革命 1.1 类型安全的进化史 前泛型时代的类型转换隐患 代码的血泪史(Java 1.4版示例): List rawList new ArrayList(); rawList.add("Java"); rawList.add(Integer.valueOf(42)); // 编译通过// 灾难在运行时爆发…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...