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

LeetCode 0040.组合总和 II：回溯 + 剪枝

news 来源：原创 2025/5/18 5:29:33

【LetMeFly】40.组合总和 II：回溯 + 剪枝

力扣题目链接：https://leetcode.cn/problems/combination-sum-ii/

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

解题方法：回溯（剪枝）

类似39.组合总和：回溯 + 剪枝，但这道题比较困难的地方在于，candidates中有重复的元素，而答案中不能有重复的数组。

怎么办呢，排序呗。刚开始还和之前一样走正常流程：

如果target已经达到则将当前方案加入答案数组。
如果已超target则直接返回
选当前元素并回溯
不选当前元素

不同之处在于，不选当前元素时，要保证选择的下一个元素和当前元素不同。

例如[4, 4, 5]，不选第一个4的话，就不能选第二个4。

否则的话，可能会出现第一个4和5、第二个4和5这两种相同的方案。

时间复杂度 $O(len(candidates)^2)$
空间复杂度 $O (l e n (c an d i d a t es))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-01-26 07:27:24* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-26 07:57:37*/
class Solution {
private:vector<vector<int>> ans;vector<int> now;void dfs(vector<int>& c, int target, int index) {// 组合成功if (!target) {ans.push_back(now);return;}// 不再可能if (index == c.size() || target < 0) {return;}// 选当前now.push_back(c[index]);dfs(c, target - c[index], index + 1);now.pop_back();// 不选当前递归下一个int next = index;while (++next < c.size() && c[next] == c[index]);dfs(c, target, next);}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());dfs(candidates, target, 0);return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-01-26 07:58:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-26 08:01:59
'''
from typing import Listclass Solution:def dfs(self, target: int, index: int) -> None:if not target:self.ans.append([i for i in self.now])returnif index == len(self.c) or target < 0:returnself.now.append(self.c[index])self.dfs(target - self.c[index], index + 1)self.now.pop()next = index + 1while next < len(self.c) and self.c[next] == self.c[index]:next += 1self.dfs(target, next)def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.c = candidatesself.ans = []self.now = []self.dfs(target, 0)return self.ans

Java

/** @Author: LetMeFly* @Date: 2025-01-26 08:02:41* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-26 08:10:08*/
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;class Solution {private List<List<Integer>> ans;private List<Integer> now;private int[] c;private void dfs(int target, int index) {if (target == 0) {ans.add(new ArrayList<>(now));return;}if (index == c.length || target < 0) {return;}now.add(c[index]);dfs(target - c[index], index + 1);now.remove(now.size() - 1);int next = index;while (++next < c.length && c[next] == c[index]);dfs(target, next);}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);c = candidates;ans = new ArrayList<>();now = new ArrayList<>();dfs(target, 0);return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-01-26 08:47:10* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-26 09:01:49* @Descreption: AC,100.00%,34.12%*/
package mainimport "sort"func dfs(c []int, target int, now []int, index int, ans *[][]int) {if target == 0 {*ans = append(*ans, append([]int{}, now...))return}if index == len(c) || target < 0 {return}now = append(now, c[index])dfs(c, target - c[index], now, index + 1, ans)now = now[:len(now) - 1]next := index + 1for next < len(c) && c[next] == c[index] {next++}dfs(c, target, now, next, ans)
}func combinationSum2(candidates []int, target int) (ans [][]int) {var now []intsort.Ints(candidates)dfs(candidates, target, now, 0, &ans)return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/145363298

LeetCode 0040.组合总和 II：回溯 + 剪枝

【LetMeFly】40.组合总和 II：回溯剪枝力扣题目链接：https://leetcode.cn/problems/combination-sum-ii/ 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates…...

编程日记 2025/5/18 5:29:33

springCload快速入门

原作者：3. SpringCloud - 快速通关前置知识： Java17及以上、MavenSpringBoot、SpringMVC、MyBatisLinux、Docker 1. 分布式基础 1.1. 微服务微服务架构风格，就像是把一个单独的应用程序开发为一套小服务，每个小服务运行在自…...

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

实现使用K210单片机进行猫脸检测，并在检测到猫脸覆盖屏幕50%以上时执行特定操作

要实现使用K210单片机进行猫脸检测，并在检测到猫脸覆盖屏幕50%以上时执行特定操作，以及通过WiFi上传图片到微信小程序，并在微信小程序中上传图片到开发板进行训练，可以按照以下步骤进行： 1. 硬件连接确保K210开发板…...

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

FlashAttention v1 论文解读

论文标题：FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness 论文地址：https://arxiv.org/pdf/2205.14135 FlashAttention 是一种重新排序注意力计算的算法，它无需任何近似即可加速注意力计算并减少内存占用。…...

编程日记 2025/5/18 5:26:41

Kafka 副本机制（包含AR、ISR、OSR、HW 和 LEO 介绍）

文章目录 Kafka 副本机制（包含AR、ISR、OSR、HW 和 LEO 介绍）1. 副本的基本概念2. 副本同步和一致性2.1 AR（Assigned Replicas）2.2 ISR（In-Sync Replicas）2.3 OSR（Out-of-Sync Replicas&#xf…...

编程日记 2025/5/18 5:23:53

QtCreator在配置Compilers时,有一个叫ABI的选项,那么什么是ABI？

问题提出 QtCreator在配置Compilers时,有一个叫ABI的选项,那么什么是ABI？ ABI（Application Binary Interface）介绍 ABI（Application Binary Interface，应用二进制接口）是指应用程序与操作系统或其他程序…...

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

ResNet--深度学习中的革命性网络架构

一、引言在深度学习的研究和应用中，网络架构的设计始终是一个关键话题。随着计算能力和大数据的不断提升，深度神经网络逐渐成为解决复杂任务的主流方法。然而，随着网络层数的增加，训练深度神经网络往往面临梯度消失或梯度爆炸的…...

编程日记 2025/5/18 5:09:23

【软件测试项目实战】以淘宝网购物车管理功能为例

一、测试功能模块分析选择淘宝网购物车管理功能进行测试，核心子功能包含： 单商品添加/删除购物车商品数量修改多商品勾选与批量删除失效商品识别与处理二、测试用例设计方法论应用 1. 等价类划分法（商品添加操作） 分析&…...

编程日记 2025/5/17 8:30:36

Go 中 defer 的机制

文章目录 Go 语言中 defer 的底层机制与实战解析一、defer 的执行顺序：后进先出（LIFO）示例 ：多个 defer 的执行顺序二、defer 的参数预计算：值拷贝的陷阱示例 ：参数预计算的影响三、defer 与闭包&#xf…...

编程日记 2025/5/18 5:23:53

智能小区物业管理系统推动数字化转型与提升用户居住体验

内容概要在当今快速发展的社会中，智能小区物业管理系统的出现正在改变传统的物业管理方式。这种系统不仅仅是一种工具，更是一种推动数字化转型的重要力量。它通过高效的技术手段，将物业管理与用户居住体验紧密结合，无疑为社区带…...

编程日记 2025/5/17 10:34:34

【memgpt】letta 课程4：基于latta框架构建MemGpt代理并与之交互

Lab 3: Building Agents with memory 基于latta框架构建MemGpt代理并与之交互理解代理状态，例如作为系统提示符、工具和agent的内存查看和编辑代理存档内存MemGPT 代理是有状态的 agents的设计思路每个步骤都要定义代理行为 Letta agents persist information over time and…...

编程日记 2025/5/18 5:26:40

HTML DOM 对象

HTML DOM 对象引言 HTML DOM（文档对象模型）是现代网页开发的核心技术之一。DOM 将 HTML 或 XML 文档结构化，使其成为可编程的对象。通过 DOM，开发者可以轻松地操作网页内容、样式和结构。本文将详细介绍 HTML DOM 对象的相关知识，包括其概念、结构、操作方法以及在实际…...

编程日记 2025/5/17 21:48:20

高温环境对电机性能的影响与LabVIEW应用

电机在高温环境下的性能可能受到多种因素的影响，尤其是对于持续工作和高负荷条件下的电机。高温会影响电机的效率、寿命以及可靠性，导致设备出现过热、绝缘损坏等问题。因此，在设计电机控制系统时，特别是在高温环境下，…...

编程日记 2025/5/18 4:55:02

【09-电源线布线与覆铜 GND与转孔】

走线从接触点处走线 TYPEC画线-加铜皮 1.关闭不需要的层(锡膏层和阻焊层和机械层) 紫色阻焊层 L: 顶层锡膏底层锡膏顶层阻焊底层阻焊 2.修改线框或者贴铜 3.顶层走不过去:打四个孔核心:走线-打孔-贴铜皮设置孔的参数:大小和人为盖有挨一下其他才会有网络 4个孔也要贴…...

编程日记 2025/5/18 5:28:12

算法题（48）：反转链表

审题： 需要我们将链表反转并返回头结点地址思路： 一般在面试中，涉及链表的题会主要考察链表的指向改变，所以一般不会允许我们改变节点val值。这里是单向链表，如果要把指向反过来则需要同时知道前中后三个节点&#x…...

编程日记 2025/5/18 5:07:53

C++ 泛型编程指南02 (模板参数的类型推导)

文章目录一深入了解C中的函数模板类型推断什么是类型推断？使用Boost TypeIndex库进行类型推断分析示例代码关键点解析 2. 理解函数模板类型推断2.1 指针或引用类型2.1.1 忽略引用2.1.2 保持const属性2.1.3 处理指针类型 2.2 万能引用类型2.3 传值方式2.4 传值方式…...

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

穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞单词搜索

题解如下题目：解析决策树：代码设计： 代码： 题目： 解析决策树： 代码设计： 代码： class Solution {private boolean[][] visit;//标记使用过的数据int m,n;//行，列char…...

编程日记 2025/5/17 19:12:52

一、point.rs源码 use super::UnknownUnit; use crate::approxeq::ApproxEq; use crate::approxord::{max, min}; use crate::length::Length; use crate::num::*; use crate::scale::Scale; use crate::size::{Size2D, Size3D}; use crate::vector::{vec2, vec3, Vector2D, V…...

编程日记 2025/5/16 11:34:43

基于vue船运物流管理系统设计与实现(源码+数据库+文档)

船运物流管理系统目录目录基于springboot船运物流管理系统设计与实现一、前言二、系统功能设计三、系统实现 1、管理员登录 2、货运单管理 3、公告管理 4、公告类型管理 5、新闻管理 6、新闻类型管理四、数据库设计 1、实体ER图五、核心代码六、论文参考…...

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

海思ISP开发说明

1、概述 ISP（Image Signal Processor）图像信号处理器是专门用于处理图像信号的硬件或处理单元，广泛应用于图像传感器（如 CMOS 或 CCD 传感器）与显示设备之间的信号转换过程中。ISP通过一系列数字图像处理算法完成对数字…...

编程日记 2025/5/18 4:50:06

【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】2.12 连续数组：为什么contiguous这么重要？

2.12 连续数组：为什么contiguous这么重要？ 目录 #mermaid-svg-wxhozKbHdFIldAkj {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-wxhozKbHdFIldAkj .error-icon{fill:#552222;}#mermaid-svg-…...

编程日记 2025/5/18 4:50:06

Chromium132 编译指南 - Android 篇（一）：编译前准备

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

编程日记 2025/5/13 0:12:35

Jenkins未在第一次登录后设置用户名，第二次登录不进去怎么办？

Jenkins在第一次进行登录的时候，只需要输入Jenkins\secrets\initialAdminPassword中的密码，登录成功后，本次我们没有修改密码，就会导致后面第二次登录，Jenkins需要进行用户名和密码的验证，但是我们根本就没…...

编程日记 2025/5/18 5:16:09

#define，源文件与头文件，赋值表达式

1.#define 1.1定义 #define 是一个预处理指令，用于定义宏宏，是预处理阶段（在编译之前）由预处理器处理的代码片段 1.2使用 1.2.1 #define 可以定义常量 #define PI 3.14159 1.2.2 #define 可以定义宏函数 #define SQUARE(x) ((…...

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

wordpress外贸独立站常用询盘软件

LiveChat LiveChat是一家提供实时聊天软件的公司，帮助企业通过其平台与客户进行即时通讯，提高客户满意度和忠诚度。他们的产品允许企业在网站、应用程序或电子邮件等多个渠道与客户互动，从而提升客户体验并促进销售增长。 LiveChat的软件特…...

编程日记 2025/5/18 5:17:52

网络爬虫学习：应用selenium获取Edge浏览器版本号，自动下载对应版本msedgedriver，确保Edge浏览器顺利打开。

一、前言我从24年11月份开始学习网络爬虫应用开发，经过2个来月的努力，于1月下旬完成了开发一款网络爬虫软件的学习目标。这里对本次学习及应用开发进行一下回顾总结。前几天我已经发了一篇日志（网络爬虫学习：应用selenium从搜…...

编程日记 2025/5/18 5:19:14

Zookeeper入门部署（单点与集群）

本篇文章基于docker方式部署zookeeper集群，请先安装docker 目录 1. docker初期准备 2.启动zookeeper 2.1 单点部署 2.2 集群部署 3. Linux脚本实现快速切换启动关闭 1. docker初期准备拉取zookeeper镜像 docker pull zookeeper:3.5.6 如果拉取时间过长&#xf…...

编程日记 2025/5/18 4:59:57

2025最新在线模型转换工具onnx转换ncnn，mnn，tengine等

文章目录引言最新网址地点一、模型转换1. 框架转换全景图2. 安全的模型转换3. 网站全景图二、转换说明三、模型转换流程图四、感谢引言在yolov5，yolov8，yolov11等等模型转换的领域中，时间成本常常是开发者头疼的问题。最近发现一个超棒的…...

编程日记 2025/5/18 5:06:09

文件读写操作

写入文本文件 #include <iostream> #include <fstream>//ofstream类需要包含的头文件 using namespace std;void test01() {//1、包含头文件 fstream//2、创建流对象ofstream fout;/*3、指定打开方式：1.ios::out、ios::trunc 清除文件内容后打开2.ios:…...

编程日记 2025/5/18 5:19:14

AJAX XML

AJAX XML 引言随着互联网技术的不断发展，Web应用对用户交互性和实时性的要求越来越高。AJAX（Asynchronous JavaScript and XML）技术的出现，为Web应用开发提供了强大的支持。AJAX技术允许Web应用在不重新加载整个页面的情况下，与服务器进行异步通信。XML作为数据传输格式…...

编程日记 2025/5/18 4:51:26

Linux文件原生操作

Linux 中一切皆文件，那么 Linux 文件是什么？ 在 Linux 中的文件可以是：传统意义上的有序数据集合，即：文件系统中的物理文件也可以是：设备，管道，内存。。。(Linux 管理的一切对象…...

编程日记 2025/5/13 5:38:02

JavaScript常用的内置构造函数

JavaScript作为一种广泛应用的编程语言，提供了丰富的内置构造函数，帮助开发者处理不同类型的数据和操作。这些内置构造函数在创建和操作对象时非常有用。本文将详细介绍JavaScript中常用的内置构造函数及其用途。常用内置构造函数概述 1. Object Obj…...

编程日记 2025/5/17 23:25:51

Shell篇-字符串处理

目录 1.变量引用 2.获取字符串长度 3.字符串截取 4.删除子字符串 5.字符串替换总结： Bash（Shell 脚本）中的字符串处理语法。以下是对其的介绍和总结：Bash 变量可以使用不同的语法来获取、修改和删除字符串的内容。图片中列…...

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

Arduino大师练成手册 -- 控制 AS608 指纹识别模块

要在 Arduino 上控制 AS608 指纹识别模块，你可以按照以下步骤进行： 硬件连接连接指纹模块：将 AS608 指纹模块与 Arduino 连接。通常，AS608 使用 UART 接口进行通信。你需要将 AS608 的 TX、RX、VCC 和 GND 引脚分别连接到 Ardu…...

编程日记 2025/5/18 5:17:52

C++ Primer 命名空间的using声明

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/5/13 23:38:39

C#，入门教程(12)——数组及数组使用的基础知识

上一篇： C#，入门教程(11)——枚举（Enum）的基础知识和高级应用https://blog.csdn.net/beijinghorn/article/details/123917587https://blog.csdn.net/beijinghorn/article/details/123917587 数组是一种数据集合，是一组…...

编程日记 2025/5/17 5:26:12

深入浅出并查集（不相交集合实现思路）

引言并查集（Disjoint Set Union，简称DSU）是一种用于处理一些不交集的合并及查询问题。它主要支持两种操作：查找（Find）和合并（Union）。查找：确定某个元素属于哪一个子…...

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

M｜哪吒之魔童闹海

rating: 8.5 豆瓣: 8.5 上映时间: “2025” 类型: M动画导演: 饺子主演: 国家/地区: 中国大陆片长/分钟: 144分钟 M｜哪吒之魔童闹海制作精良，除了剧情逻辑有一点瑕疵，各方面都很到位。总体瑕不掩瑜。上映时间： &…...

编程日记 2025/5/18 4:48:16

【c++】类与对象详解

目录面向过程思想和面向对象思想类的定义引入类的关键字类定义的两种方式类的访问限定符类的作用域类大小的计算封装 this指针类的6个默认成员函数构造函数初步理解构造函数深入理解构造函数初始化列表单参数构造函数引发的隐式类型转换析构函数拷贝构造函数赋值运算符重载运…...

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

LabVIEW如何有效地进行数据采集？

数据采集（DAQ）是许多工程项目中的核心环节，无论是测试、监控还是控制系统，准确、高效的数据采集都是至关重要的。LabVIEW作为一个图形化编程环境，提供了丰富的功能来实现数据采集，确保数据的实时性与可靠性…...

编程日记 2025/5/18 4:56:52

Golang 并发机制-4：用Mutex管理共享资源

并发性是Go的强大功能之一，它允许多个线程（并发线程）同时执行。然而，权力越大，责任越大。当多个例程并发地访问和修改共享资源时，可能会导致数据损坏、竞争条件和不可预测的程序行为。为了解决这些问题&…...

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

如何用微信小程序写春联

生活没有模板，只需心灯一盏。如果笑能让你释然，那就开怀一笑；如果哭能让你减压，那就让泪水流下来。如果沉默是金，那就不用解释；如果放下能更好地前行，就别再扛着。一、引入 Vant UI 1、通过 npm 安装 npm i @vant/weapp -S --production 2、修改 app.json …...

编程日记 2025/5/18 3:47:06

从零开始：用Qt开发一个功能强大的文本编辑器——WPS项目全解析

文章目录引言项目功能介绍1. **文件操作**2. **文本编辑功能**3. **撤销与重做**4. **剪切、复制与粘贴**5. **文本查找与替换**6. **打印功能**7. **打印预览**8. **设置字体颜色**9. **设置字号**10. **设置字体**11. **左对齐**12. **右对齐**13. **居中对齐**14. **两侧对…...

编程日记 2025/5/13 7:14:02

LLMs之OpenAI o系列：OpenAI o3-mini的简介、安装和使用方法、案例应用之详细攻略

LLMs之OpenAI o系列：OpenAI o3-mini的简介、安装和使用方法、案例应用之详细攻略目录相关文章 LLMs之o3：《Deliberative Alignment: Reasoning Enables Safer Language Models》翻译与解读 LLMs之OpenAI o系列：OpenAI o3-mini的简介、安…...

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

DeepSeek-R1 低成本训练的根本原因是？

在人工智能领域，大语言模型（LLM）正以前所未有的速度发展，驱动着自然语言处理、内容生成、智能客服等众多应用的革新。然而，高性能的背后往往是高昂的训练成本，动辄数百万美元的投入让许多企业和研究机构望而…...

编程日记 2025/5/18 2:48:33

C语言：结构体

一，结构体 C语⾔已经提供了内置类型，如：char、short、int、long、float、double等，但是只有这些内置类型还是不够的，假设我想描述学⽣，描述⼀本书，这时单⼀的内置类型是不⾏的。描述⼀个学⽣需…...

编程日记 2025/5/12 19:58:59

java练习（5）

ps:题目来自力扣给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这…...

编程日记 2025/5/15 14:24:07

【高等数学】贝塞尔函数

贝塞尔函数（Bessel functions）是数学中一类重要的特殊函数，通常用于解决涉及圆对称或球对称的微分方程。它们在物理学、工程学、天文学等多个领域都有广泛的应用，例如在波动方程、热传导方程、电磁波传播等问题中。贝塞尔函数的…...

编程日记 2025/5/15 8:38:29

贪吃蛇实现

1.资料来源 https://learn.microsoft.com/zh-cn/windows/console/getstdhandle 2.前言简介贪吃蛇是久负盛名的游戏，和俄罗斯方块、扫雷等游戏位列于经典游戏的行列。《贪食蛇》中玩家控制一条不断移动的蛇，在屏幕上吃掉出现的食物。每吃掉一个食物…...

编程日记 2025/5/15 5:35:28

Windows电脑本地部署运行DeepSeek R1大模型（基于Ollama和Chatbox）

文章目录一、环境准备二、安装Ollama2.1 访问Ollama官方网站2.2 下载适用于Windows的安装包2.3 安装Ollama安装包2.4 指定Ollama安装目录2.5 指定Ollama的大模型的存储目录三、选择DeepSeek R1模型四、下载并运行DeepSeek R1模型五、使用Chatbox进行交互5.1 下载Chatbox安装包…...

编程日记 2025/5/14 20:47:26

【LetMeFly】40.组合总和 II：回溯 + 剪枝

解题方法：回溯（剪枝）

AC代码

C++

Python

Java

Go

相关文章：