当前位置: 首页 > 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)); // 编译通过// 灾难在运行时爆发…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...