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

【LeetCode 刷题】回溯算法-组合问题

news 来源：原创 2025/5/18 21:04:55

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法组合问题相关的题目解析。

文章目录

77. 组合
216.组合总和III
17.电话号码的字母组合
39. 组合总和
40. 组合总和 II

77. 组合

题目链接

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:res, path = [], []def dfs(start: int, n: int) -> None:if len(path) > k or n < 0:returnif len(path) == k and n == 0:res.append(path.copy())returnfor i in range(start, 10):path.append(i)dfs(i + 1, n - i)path.pop()dfs(1, n)return res

dfs 函数的参数为起始位置；由于每个数只能用一次，因此在后序的递归过程中只需调整起始位置为上一个选择的元素的后一个位置即可，也即 dfs(i + 1)
如果 append() 的时候不添加 .copy()，则放入结果列表的仍然是原始 path 变量的引用，对 path 的修改会影响到结果列表
优化点：for 循环选择的起始位置之后的元素个数已经不足需要的元素个数了，则可以直接剪枝

216.组合总和III

题目链接

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:res, path = [], []def dfs(start: int, n: int) -> None:if len(path) == k and n == 0:res.append(path.copy())returnif len(path) > k or n < 0:returnfor i in range(start, 10):path.append(i)dfs(i + 1, n - i)path.pop()dfs(1, n)return res

dfs 的两个参数分别表示：起始位置，剩余要满足的值
相较于上题，额外添加了总和为 n 的限制

17.电话号码的字母组合

题目链接

class Solution:MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]def letterCombinations(self, digits: str) -> List[str]:res, path = [], []if not digits: return resdef dfs(start: int) -> None:if start == len(digits):res.append(''.join(path))returnfor c in self.MAPPING[int(digits[start])]:path.append(c)dfs(start + 1)path.pop()dfs(0)return res

dfs 函数的参数为起始位置，也即为在该轮递归中要处理的第 start 位 digits

39. 组合总和

题目链接

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res, path = [], []def dfs(start: int, target: int) -> None:if target < 0:returnif target == 0:res.append(path.copy())for i in range(start, len(candidates)):if i > start and candidates[i] == candidates[i-1]:continuepath.append(candidates[i])dfs(i, target - candidates[i])path.pop()dfs(0, target)return res

dfs 的两个参数分别表示：起始位置，剩余要满足的值；由于此题元素可以重复使用，因此在递归调用时，起始位置不变，即 dfs(i, ...)
此题要求结果列表中的组合不重复，通过 candidates[i] != candidates[i-1] 来保证，因为如果 candidates[i] == candidates[i-1]，则 candidates[i-1] 生成的递归树是 candidates[i] 生成的递归树的子树

40. 组合总和 II

题目链接

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:res, path = [], []candidates.sort()def dfs(start: int, target: int) -> None:if target < 0:returnif target == 0:res.append(path.copy())for i in range(start, len(candidates)):if i > start and candidates[i] == candidates[i-1]:continuepath.append(candidates[i])dfs(i + 1, target - candidates[i])path.pop()dfs(0, target)return res

此题与上题的不同点：每个元素只能使用一次，且原始 candidates 中是存在重复元素的，例如有两个 1，同时选择这两个 1 是没有问题的
回溯之前需添加排序；递归调用从下一个位置开始，即 dfs(i + 1, ...)

【LeetCode 刷题】回溯算法-组合问题

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法组合问题相关的题目解析。文章目录 77. 组合216.组合总和III17.电话号码的字母组合39. 组合总和40. 组合总和 II 77. 组合题目链接 class Solution:def combinationSum3(self, k: int, n: int) …...

编程日记 2025/5/18 21:04:55

Automatic Prefix Caching

APC技术，遇到新prompt和老prompt前缀完全相等的，则复用老prompt的KV cache，避免重新计算。 VLLM代码实例： # set enable_prefix_cachingTrue to enable APC llm LLM(modellmsys/longchat-13b-16k,enable_prefix_cachingTrue ) 应…...

编程日记 2025/5/18 20:59:36

DDD - 领域事件_解耦微服务的关键

文章目录 Pre领域事件的核心概念领域事件的作用领域事件的识别领域事件的技术实现领域事件的运行机制案例领域事件驱动的优势 Pre DDD - 微服务设计与领域驱动设计实战(中)_ 解决微服务拆分难题 EDA - Spring Boot构建基于事件驱动的消息系统领域事件的核心概念领域事件&a…...

编程日记 2025/5/18 0:10:48

吴晓波历代经济变革得失@简明“中国经济史” - 读书笔记

目录《历代经济变革得失》读书笔记一、核心观点二、主要内容（一）导论（二）春秋战国时期（三）汉代（四）北宋（五）明清时期（六）近现代&…...

编程日记 2025/5/18 20:38:21

Ubuntu下的Doxygen+VScode实现C/C++接口文档自动生成

Ubuntu下的DoxygenVScode实现C/C接口文档自动生成 Chapter1 Ubuntu下的DoxygenVScode实现C/C接口文档自动生成1、 Doxygen简介1. 安装Doxygen1）方法一：2）方法二：2. doxygen注释自动生成插件3. doxygen注释基本语法4. doxygen的生成…...

编程日记 2025/5/18 20:48:40

论文阅读：Realistic Noise Synthesis with Diffusion Models

这篇文章是 2025 AAAI 的一篇工作，主要介绍的是用扩散模型实现对真实噪声的仿真模拟 Abstract 深度去噪模型需要大量来自现实世界的训练数据，而获取这些数据颇具挑战性。当前的噪声合成技术难以准确模拟复杂的噪声分布。我们提出一种新颖的逼真噪声合成…...

编程日记 2025/5/18 20:16:43

【Linux系统】计算机世界的基石：冯诺依曼架构与操作系统设计

文章目录一.冯诺依曼体系结构1.1 为什么体系结构中要存在内存？1.2 冯诺依曼瓶颈二.操作系统2.1 设计目的2.2 系统调用与库函数一.冯诺依曼体系结构冯诺依曼体系结构（Von Neumann Architecture）是计算机的基本设计理念之一，由…...

编程日记 2025/5/18 3:39:50

p1044 栈

两种递推细节不同 1,将1和n在序列末尾的情况单独放出来处理，因为dp[0]0； 2,将所有情况统一处理，这种情况就要要求dp[1]1; 这里的n在解题中可以看做是元素数量思路是，根据出栈最后一个元素,统计它前面的元素数量的输出序列数和…...

编程日记 2025/5/18 20:16:42

x86-64数据传输指令

关于汇编语言一些基础概念的更详细的介绍，可移步MIPS指令集（一）基本操作_mips指令 sw-CSDN博客该指令集中一个字2字节。该架构有16个64位寄存器，名字都以%r开头，每个寄存器的最低位字节，低1~2位字节&…...

编程日记 2025/5/18 17:34:03

C++11新特性之lambda表达式

1.介绍 C11引入了lambda表达式。lambda表达式提供一种简洁的方式来定义匿名函数对象，使得在需要临时定义一个函数时非常方便。 2.lambda表达式用法 lambda表达式的基本用法为： [捕获列表]（参数列表）->返回类型 { 函数体 …...

编程日记 2025/5/16 11:46:22

基于液晶屏外设写的. main.c #include <REGX52.H> #include "LCD1602.h" #include "MatrixKey.h" #include "Sleep.h" long password1234; long resNum0; int status0,res0,k1500; long birth2005; void main(){LCD_Init();LCD_ShowStr…...

编程日记 2025/5/18 20:34:40

如何使用C#的using语句释放资源？什么是IDisposable接口？与垃圾回收有什么关系？

在 C# 中，using语句用于自动释放实现了IDisposable接口的对象所占用的非托管资源，如文件句柄、数据库连接、图形句柄等。其使用方式如下：基础用法声明并初始化资源对象：在using关键字后的括号内声明并初始化一个实现了IDisposable接口的对象。使用资源：在using语句块内…...

编程日记 2025/5/18 20:11:18

【Unity3D】实现横版2D游戏——单向平台（简易版）

目录问题项目Demo直接使用免费资源：Hero Knight - Pixel Art （Asset Store搜索） 打开Demo场景，进行如下修改，注意Tag是自定义标签SingleDirCollider using System.Collections; using System.Collections.Generic;…...

编程日记 2025/5/18 2:20:22

BW AO/工作簿权限配置

场景： 按事业部配置工作簿权限； 1、创建用户事务码：SU01，用户主数据的维护，可以创建、修改、删除、锁定、解锁、修改密码等用户设置详情页 2、创建权限角色用户的权限菜单是通过权限角色分配来实现的 2.1、自定…...

编程日记 2025/5/18 10:06:17

TensorFlow 示例摄氏度到华氏度的转换（一）

TensorFlow 实现神经网络模型来进行摄氏度到华氏度的转换，可以将其作为一个回归问题来处理。我们可以通过神经网络来拟合这个简单的转换公式。 1. 数据准备与预处理 2. 构建模型 3. 编译模型 4. 训练模型 5. 评估模型 6. 模型应用与预测 7. 保存与加载模型 …...

编程日记 2025/5/18 20:48:40

一文讲解JVM中的G1垃圾收集器

接上一篇博文，这篇博文讲下JVM中的G1垃圾收集器 G1在JDK1.7时引入，在JDK9时取代了CMS成为默认的垃圾收集器； G1把Java堆划分为多个大小相等的独立区域Region，每个区域都可以扮演新生代（Eden和Survivor）或老…...

编程日记 2025/5/18 17:26:36

图书管理系统 Axios 源码__获取图书列表

目录核心功能源码介绍 1. 获取图书列表技术要点适用人群本项目是一个基于 HTML Bootstrap JavaScript Axios 开发的图书管理系统，可用于添加、编辑、删除和管理图书信息，适合前端开发者学习前端交互设计、Axios 数据请求以及 Bootstrap 样…...

编程日记 2025/5/18 20:52:24

mac和linux传输文件

1、使用scp命令传输 # 上传 wenqiangwq ~ % scp -pr -P 22 nginx.yaml root192.168.1.15:/tmp/ root192.168.1.15s password: nginx.yaml 100% 1736 332.4KB/s 00:00# 下载 wenqiangwq ~ % scp -pr -P 22 root192.168.1.15:/tmp/ngin…...

编程日记 2025/5/18 20:54:15

[CVPR 2024] AnyDoor: Zero-shot Object-level Image Customization

github.com/ali-vilab/AnyDoor.写在前面： 【论文速读】按照#论文十问#提炼出论文核心知识点，方便相关科研工作者快速掌握论文内容。过程中并不对论文相关内容进行翻译。博主认为翻译难免会损坏论文的原本含义，也鼓励诸位入门级科研人员阅读文…...

编程日记 2025/5/18 20:31:17

(动态规划路径基础最小路径和)leetcode 64

视频教程 1.初始化dp数组，初始化边界 2、从[1行到n-1行][1列到m-1列]依次赋值 #include<vector> #include<algorithm> #include <iostream>using namespace std; int main() {vector<vector<int>> grid { {1,3,1},{1,5,1},{4,2,1}…...

编程日记 2025/5/14 22:48:56

跨组织环境下 MQTT 桥接架构的评估

论文标题中文标题： 跨组织环境下 MQTT 桥接架构的评估英文标题： Evaluation of MQTT Bridge Architectures in a Cross-Organizational Context 作者信息 Keila Lima, Tosin Daniel Oyetoyan, Rogardt Heldal, Wilhelm Hasselbring Western Norway …...

编程日记 2025/5/18 13:00:10

2025年1月22日（网络编程 udp）

系统信息： ubuntu 16.04LTS Raspberry Pi Zero 2W 系统版本： 2024-10-22-raspios-bullseye-armhf Python 版本：Python 3.9.2 已安装 pip3 支持拍摄 1080p 30 (1092*1080), 720p 60 (1280*720), 60/90 (640*480) 已安装 vim 已安装 git 学习…...

编程日记 2025/5/16 14:21:48

基于 STM32 的智能电梯控制系统

1. 引言随着城市化进程的加速，高层建筑日益增多，电梯作为垂直交通工具的重要性愈发凸显。传统电梯控制系统在运行效率、安全性和智能化程度上已难以满足现代需求。智能电梯控制系统能够实时监测电梯的运行状态、乘客需求，并根据这些信息优化…...

编程日记 2025/5/17 17:39:31

使用 Docker(Podman) 部署 MongoDB 数据库及使用详解

在现代开发环境中，容器化技术（如 Docker 和 Podman）已成为部署和管理应用程序的标准方式。本文将详细介绍如何使用 Podman/Docker 部署 MongoDB 数据库，并确保其他应用程序容器能够通过 Docker 网络成功连接到 MongoDB。我们将逐步…...

编程日记 2025/5/15 21:07:31

npm 和 pip 安装中常见问题总结

安装路径的疑惑：NPM 和 PIP 的安装机制 NPM 安装路径规则： 依赖安装在项目目录下： 当你运行 npm install --save-dev jest，它会在当前目录（例如 F:\）下创建一个 node_modules 文件夹，把 jest 安…...

编程日记 2025/5/13 5:39:54

golang面试题

目录 go版本新增功能 Go 1.11 Go 1.18 Go 1.5 go关键字 ： 1. 用于声明的关键字 2. 控制流关键字 3. 包相关关键字 4. 并发相关关键字 5. 异常处理关键字 6. 接口和类型断言关键字 go数据类型： 复合数据类型引用数据类型接口类型 GC垃…...

编程日记 2025/5/17 17:19:48

基于UKF-IMM无迹卡尔曼滤波与交互式多模型的轨迹跟踪算法matlab仿真,对比EKF-IMM和UKF

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述基于UKF-IMM无迹卡尔曼滤波与交互式多模型的轨迹跟踪算法matlab仿真,对比EKF-IMM和UKF。 2.测试软件版本以及运行结果展示 MATLAB2022A版本运行 3.核心程序 .…...

编程日记 2025/5/14 5:25:49

Install Python

目录 1.Install Python 1.安装Python 3 2.在Windows上安装Python 3.在Mac上安装Python 4.在Linux上安装Python 5.运行Python 2.Python解释器 1.CPython 2.IPython 3.PyPy 4.Jython 5.IronPython 6.小结 1.Install Python 因为Python是跨平台的，它可以…...

编程日记 2025/5/18 1:17:10

云计算部署模式全面解析

目录引言公有云私有云混合云三种部署模式的对比选择建议未来趋势结语 1. 引言随着云计算技术的快速发展,企业在选择云部署模式时面临着多种选择。本文将深入探讨云计算的三种主要部署模式:公有云、私有云和混合云,帮助读者全面了解它们的特点、优势及适用场景。 © iv…...

编程日记 2025/5/14 17:29:28

tomcat核心组件及原理概述

目录 1. tomcat概述 1.1 概念 1.2 官网地址 2. 基本使用 2.1下载 3. 整体架构 3.1 核心组件 3.2 从web.xml配置和模块对应角度 3.3 如何处理请求 4. 配置JVM参数 5. 附录 1. tomcat概述 1.1 概念什么是tomcat Tomcat是一个开源、免费、轻量级的Web服务器。 Tomca…...

编程日记 2025/5/18 12:25:34

GIS教程：全国数码商城系统

文章目录注册高德地图API普通网页中测试地图加载地图添加标记地图配置点标记 Marker添加弹框创建vue项目并添加高德地图创建项目加载高德地图项目首页布局封装axios和配置代理服务器获取城市热门信息获取城市区县信息获取区县商城信息获取指定城市区县的经纬度坐标将地图缩放到…...

编程日记 2025/5/16 17:40:56

Level DB --- table.format

table.format是Level DB中table序列化、反序列化重要的辅助类。它用来定义序列化、反序列化的核心结构体和操作实现。 BlockHandle table.format中的BlockHandle类主要用来记录当前block在总的序列化中的offset位置，以及当前block的size，这里面的Block…...

编程日记 2025/5/14 7:39:49

《编写可读代码的艺术》读书笔记

1. 写在前面借着春节放假的几天， 读了下《编写可读代码的艺术》这本书， 这本书不是很长，主要关注代码的一些编写细节，比如方法命名，函数命名，语句组织，任务分解等， 旨在让写的代码…...

编程日记 2025/5/14 22:48:53

（9）下：学习与验证 linux 里的 epoll 对象里的 EPOLLIN、 EPOLLHUP 与 EPOLLRDHUP 的不同。小例子的实验

（4）本实验代码的蓝本，是伊圣雨老师里的课本里的代码，略加改动而来的。以下是服务器端的代码： 每当收到客户端的报文时，就测试一下对应的 epoll 事件里的事件标志，不读取报文内容，…...

编程日记 2025/5/15 3:48:37

MySQL基础-多表查询

多表查询-多表关系多表查询-概述例如执行下行sql语句就会出现笛卡尔积： select *from emp,dept; --消除笛卡尔积 select * from emp,dept where emp.dept_id dept.id; 多表查询-查询分类多表查询-连接查询-内连接 --内连接演示 --1.查询每一个员工的姓名,及关…...

编程日记 2025/5/18 18:02:37

RK3568 opencv播放视频

文章目录一、opencv相关视频播放类1. `cv::VideoCapture` 类主要构造方法：主要方法：2. 视频播放基本流程代码示例：3. 获取和设置视频属性4. 结合 FFmpeg 使用5. OpenCV 视频播放的局限性6. 结合 Qt 实现更高级的视频播放总结二、QT中的代码实现一、opencv相关视频播放类在…...

编程日记 2025/5/14 20:18:40

C++中的类型转换

文章目录一、概述二、隐式类型转换（Implicit Conversion）三、显式类型转换（Explicit Conversion）四、C 风格类型转换一、概述 C 提供了多种类型转换（Type Conversion）方式，以便在不同类型的数…...

编程日记 2025/5/16 10:39:57

day7手机拍照装备

对焦对不上：1、光太暗；2、离太近；3、颜色太单一没有区分点滤镜可以后期P 渐变灰滤镜：均衡色彩，暗的地方亮一些，亮的地方暗一些中灰滤镜：减少光差手机支架：最基本70cm即可手…...

编程日记 2025/5/12 4:09:29

Joplin 插件在Vscode中无法显示图片

1.问题在vscode里面装好joplin插件之后，无法显示图片内容。粘贴的图片可以再vscode中显示，无法再joplin客户端显示 2.解决方法这种情况是因为和vscode自带的MD编辑器的预览模式有冲突，或者没用通过专用方式上传图片。方法一&#xff…...

编程日记 2025/5/15 4:57:43

ReentrantReadWriteLock源码分析

文章目录概述一、状态位设计二、读锁三、锁降级机制四、写锁总结概述 ReentrantReadWriteLock（读写锁）是对于ReentranLock（可重入锁）的一种改进，在可重入锁的基础上，进行了读写分离。适用于读多写少的场景…...

编程日记 2025/5/17 16:38:29

ChatGPT-4o和ChatGPT-4o mini的差异点

在人工智能领域，OpenAI再次引领创新潮流，近日正式发布了其最新模型——ChatGPT-4o及其经济实惠的小型版本ChatGPT-4o Mini。这两款模型虽同属于ChatGPT系列，但在性能、应用场景及成本上展现出显著的差异。本文将通过图文并茂的方式&#xff0…...

编程日记 2025/5/16 10:03:19

小程序设计和开发：什么是竞品分析，如何进行竞品分析

一、竞品分析的定义竞品分析是指对竞争对手的产品进行深入研究和比较，以了解市场动态、发现自身产品的优势和不足，并为产品的设计、开发和营销策略提供参考依据。在小程序设计和开发中，竞品分析可以帮助开发者了解同类型小程序的功能、用户体…...

编程日记 2025/5/17 20:01:12

计算机网络之计算机网络的分类

计算机网络可以根据不同的角度进行分类，以下是几种常见的分类方式： 1. 按照规模和范围： 局域网（LAN，Local Area Network）：覆盖较小范围（例如一个建筑物或校园）&#xf…...

编程日记 2025/5/17 16:38:22

什么是门控循环单元？

一、概念门控循环单元（Gated Recurrent Unit，GRU）是一种改进的循环神经网络（RNN），由Cho等人在2014年提出。GRU是LSTM的简化版本，通过减少门的数量和简化结构，保留了LSTM的长时间依赖…...

编程日记 2025/5/16 20:34:24

ESP32-c3实现获取土壤湿度（ADC模拟量）

1硬件实物图 2引脚定义 3使用说明 4实例代码 // 定义土壤湿度传感器连接的模拟输入引脚 const int soilMoisturePin 2; // 假设连接到GPIO2void setup() {// 初始化串口通信Serial.begin(115200); }void loop() {// 读取土壤湿度传感器的模拟值int sensorValue analogRead…...

编程日记 2025/5/17 15:57:41

获取snmp oid的小方法1（随手记）

snmpwalk遍历设备的mib # snmpwalk -v <SNMP version> -c <community-id> <IP> . snmpwalk -v 2c -c test 192.168.100.201 .根据获取的值，找到某一个想要的值的oid # SNMPv2-MIB::sysName.0 STRING: test1 [rootzabbix01 fonts]# snmpwalk -v…...

编程日记 2025/5/18 0:59:27