【算法】回溯算法专题② ——组合型回溯 + 剪枝 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)); // 编译通过// 灾难在运行时爆发…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...