当前位置: 首页 > news >正文

【算法】回溯算法专题② ——组合型回溯 + 剪枝 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&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以…...

LeetCode:121.买卖股票的最佳时机1

跟着carl学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;121.买卖股票的最佳时机1 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票…...

pytorch生成对抗网络

人工智能例子汇总&#xff1a;AI常见的算法和例子-CSDN博客 生成对抗网络&#xff08;GAN&#xff0c;Generative Adversarial Network&#xff09;是一种深度学习模型&#xff0c;由两个神经网络组成&#xff1a;生成器&#xff08;Generator&#xff09;和判别器&#xff0…...

Visual Studio Code应用本地部署的deepseek

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

用 HTML、CSS 和 JavaScript 实现抽奖转盘效果

顺序抽奖 前言 这段代码实现了一个简单的抽奖转盘效果。页面上有一个九宫格布局的抽奖区域&#xff0c;周围八个格子分别放置了不同的奖品名称&#xff0c;中间是一个 “开始抽奖” 的按钮。点击按钮后&#xff0c;抽奖区域的格子会快速滚动&#xff0c;颜色不断变化&#xf…...

Skewer v0.2.2安装与使用-生信工具43

01 Skewer 介绍 Skewer&#xff08;来自于 SourceForge&#xff09;实现了一种基于位掩码的 k-差异匹配算法&#xff0c;专门用于接头修剪&#xff0c;特别设计用于处理下一代测序&#xff08;NGS&#xff09;双端序列。 fastp安装及使用-fastp v0.23.4&#xff08;bioinfoma…...

C语言:链表排序与插入的实现

好的!以下是一篇关于这段代码的博客文章: 从零开始:链表排序与插入的实现 在数据结构的学习中,链表是一种非常基础且重要的数据结构。今天,我们将通过一个简单的 C 语言程序,来探讨如何实现一个从小到大排序的链表,并在其中插入一个新的节点。这个过程不仅涉及链表的基…...

【Elasticsearch】doc_values 可以用于查询操作

确实&#xff0c;doc values 可以用于查询操作&#xff0c;尽管它们的主要用途是支持排序、聚合和脚本中的字段访问。在某些情况下&#xff0c;Elasticsearch 也会利用 doc values 来执行特定类型的查询。以下是关于 doc values 在查询操作中的使用及其影响的详细解释&#xff…...

深度学习深度解析:从基础到前沿

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

JVM的GC详解

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

【开源免费】基于Vue和SpringBoot的校园网上店铺系统(附论文)

本文项目编号 T 187 &#xff0c;文末自助获取源码 \color{red}{T187&#xff0c;文末自助获取源码} T187&#xff0c;文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...

测压表压力表计量表针头针尾检测数据集VOC+YOLO格式4862张4类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4862 标注数量(xml文件个数)&#xff1a;4862 标注数量(txt文件个数)&#xff1a;4862 …...

Vue 3 30天精进之旅:Day 12 - 异步操作

在现代前端开发中&#xff0c;异步操作是一个非常常见的需求&#xff0c;例如从后端API获取数据、进行文件上传等任务。Vue 3 结合组合式API和Vuex可以方便地处理这些异步操作。今天我们将重点学习如何在Vue应用中进行异步操作&#xff0c;包括以下几个主题&#xff1a; 异步操…...

【网络】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&#xff08;&#xff09; 总结 1 认识URL 什么是URI&#xff1f; 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中的函数参数传递机制允许多种灵活的参数类型&#xff0c;可以根据需求灵活配置参数&#xff0c;这使得函数具有更强大的扩展性和适应性。以下是对各类参数类型的详细说明&#xff1a; 1. 定义函数的不同参数类型 1.1 位置参数 定义方式&#xff1a;def func(a, b2) 特…...

Chromium132 编译指南 - Android 篇(一):编译前准备

1. 引言 欢迎来到《Chromium 132 编译指南 - Android 篇》系列的第一部分。本系列指南将引导您逐步完成在 Android 平台上编译 Chromium 132 版本的全过程。Chromium 作为一款由 Google 主导开发的开源浏览器引擎&#xff0c;为众多现代浏览器提供了核心驱动力。而 Android 作…...

.Net / C# 繁体中文 与 简体中文 互相转换, 支持地方特色词汇

版本号 Nuget 搜索 “OpenCCNET”, 注意别找错, 好多库的名字都差不多 支持 “繁,简” 的互相转换, 支持多个地区常用词汇的转换, 还支持 日文的新旧转换. OpenCC 在 .Net 中的实现 https://github.com/CosineG/OpenCC.NET <PackageReference Include"OpenCCNET"…...

Java泛型深度解析(JDK23)

第一章 泛型革命 1.1 类型安全的进化史 前泛型时代的类型转换隐患 代码的血泪史&#xff08;Java 1.4版示例&#xff09;&#xff1a; List rawList new ArrayList(); rawList.add("Java"); rawList.add(Integer.valueOf(42)); // 编译通过// 灾难在运行时爆发…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;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中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...