【算法】回溯算法专题② ——组合型回溯 + 剪枝 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)); // 编译通过// 灾难在运行时爆发…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
生成对抗网络(GAN)损失函数解读
GAN损失函数的形式: 以下是对每个部分的解读: 1. , :这个部分表示生成器(Generator)G的目标是最小化损失函数。 :判别器(Discriminator)D的目标是最大化损失函数。 GAN的训…...
