【LeetCode刷题】--39.组合总和

39.组合总和

image-20231122220557445

本题详解:回溯算法+剪枝

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量,是 candidates 里的属性,可以不传
     * @param target     每减去一个元素,目标值变小
     * @param path       从根结点到叶子结点的路径,是一个栈
     * @param res        结果集列表
     */
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意:由于每一个元素可以重复使用,下一轮搜索的起点依然是 i,这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/177556.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

二、类与对象(二)

8 this指针 8.1 this指针的引入 我们先来定义一个日期的类Date&#xff1a; #include <iostream> using namespace std; class Date { public:void Init(int year, int month, int day){_year year;_month month;_day day;}void Print(){cout << _year <&l…

【Python】数据类型和切片的零碎知识点

1. 数据类型 pow(a, b, c) # a^b % c print("happy {}".format(name))数字类型包括整数&#xff0c;浮点数&#xff0c;复数 0x9a表示十六进制数&#xff08;0x&#xff0c;0X开头表示十六进制&#xff09; 0b1010&#xff0c;-0B101表示二进制数&#xff08;0…

【Delphi】使用TWebBrowser执行JavaScript命令传入JSON参数执行出错解决方案

目录 一、问题背景&#xff1a; 二、实际示例&#xff1a; 三、解决方案&#xff1a; 1. Delphi 代码&#xff1a; 2. javaScript代码&#xff1a; 一、问题背景&#xff1a; 在用Delphi开发程序&#xff0c;无论是移动端还是PC端&#xff0c;都可以很方便的使用TWebBrows…

c语言-操作符详解(含优先级与结合性)

文章目录 了解什么是操作数、操作符操作数&#xff1a;操作符 操作符详解&#xff1a;1.算术操作符&#xff1a; 、- 、* 、/ 、%2.移位操作符: << >>3.位操作符: & | ^4. 赋值操作符: 、 、 - 、 * 、 / 、% 、<< 、>> 、& 、| 、^5. 单⽬操…

Java架构师软件架构风格

目录 1 数据流风格1.1 管道过滤器1.2 数据流风格的优点2 调用返回风格2.1 面向对象风格2.2 调用返回风格总结3 独立构件风格3.1 事件驱动系统风格的主要特点3.2 独立构件风格总结4 虚拟机风格4.1 虚拟机风格总结5 仓库风格5.1 仓库风格总结想学习架构师构建流程请跳转:Java架构…

接口测试快速上手指南

大量线上BUG表明&#xff0c;对接口进行测试可以有效提升产品质量&#xff0c;暴露手工测试时难以发现的问题&#xff0c;同时也能缩短测试周期&#xff0c;提升测试效率。但在实际执行过程中&#xff0c;接口测试被很多同学打上了“上手难&#xff0c;门槛高”的标签。 本文旨…

中低压MOSFET 2N7002T 60V 300mA 双N通道 采用SOT-523封装形式

2N7002KW小电流双N通道MOSFET&#xff0c;电压60V电流300mA&#xff0c;采用SOT-523封装形式。低Ros (on)的高密度单元设计&#xff0c;坚固可靠&#xff0c;具有高饱和电流能力&#xff0c;ESD防护门HBM2KV。可应用于直流/直流转换器&#xff0c;电池开关等产品应用上。

用spring发送http请求

在Spring中&#xff0c;你可以使用RestTemplate或WebClient来发送HTTP请求。下面分别给出使用这两个类的简单示例。 现在pom.xml中导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artif…

原来RocketMQ消息会重复消费是无奈的”Bug“

消息发送异常时重复发送 首先&#xff0c;我们来瞅瞅RocketMQ发送消息和消费消息的基本原理。 如图&#xff0c;简单说一下上图中的概念&#xff1a; Broker&#xff0c;就是RocketMQ的服务端&#xff0c;如上图就有两个服务实例Topic就是一类消息集合的名字Queue就是Topic的…

计算机组成原理(万字爆肝整理)

第一章 计算机系统概述 “较简单&#xff0c;不做过多赘述&#xff0c;后面会详细学到” 第一节 计算机系统层次结构 1.计算机系统的基本组成&#xff1a;硬件软件 2.计算机硬件的基本组成&#xff1a;运算器存储器控制器输入设备输出设备 3.系统软件和应用软件 系统软件…

电动汽车充放电V2G模型MATLAB代码

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 主要内容&#xff1a; 本程序主要建立电动汽车充放电V2G模型&#xff0c;采用粒子群算法&#xff0c;在保证电动汽车用户出行需求的前提下&#xff0c;为了使工作区域电动汽车尽可能多的消纳供给商场基础负荷…

pycurl>=7.43.0.5机器学习环境配置问题

去官网下载对应版本.whl文件&#xff0c;注意使用python --version提前查看 python版本信息和64bit还是32bit,下载对应版本。 cd 到该路径下&#xff0c;并pip。6

MySQL数据库时间计算的用法

今天给大家分享如何通过MySQL内置函数实现时间的转换和计算&#xff0c;在工作当中&#xff0c;测试人员经常需要查询数据库表的日期时间&#xff0c;但发现开发人员存入数据库表的形式都是时间戳形式&#xff0c;不利于测试人员查看&#xff0c;测试人员只能利用工具对时间戳进…

妥善解决需求冲突的5大技巧

在进行需求分析时&#xff0c;往往会遇到需求冲突问题&#xff0c;此问题往往导致项目进度延迟、资源浪费以及软件质量问题。因此我们需要妥善解决需求冲突问题&#xff0c;平衡各方利益&#xff0c;提高项目的成功率以及客户满意度。 一般来说&#xff0c;妥善解决需求冲突有以…

LeetCode(32)串联所有单词的子串【滑动窗口】【困难】(含图解)

目录 1.题目2.答案3.提交结果截图4.图解 链接&#xff1a; 串联所有单词的子串 1.题目 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 w…

用css实现原生form中radio单选框和input输入框的hover样式以及聚焦focus的样式

一.问题描述&#xff1a;用css实现原生form中radio单选框和input的hover已经focus的样式 在实际的开发中&#xff0c;一般公司ui都会给效果图&#xff0c;比如单选按钮radio样式&#xff0c;input输入框hover的时候样式&#xff0c;以及focus的时候样式&#xff0c;等等&#…

电脑内存升级

ddr代兼容 自从DDR内存时代开启之后&#xff0c;只要满足内存的插槽规格相同(DDR3或DDR4或DDR5即为内存规格)这一条件&#xff0c;不同品牌、不同频率以及不同容量的茶品都可以一起使用&#xff0c;除了品牌和容量的影响之外&#xff0c;不同频率的搭配可能会造成性能方面的影…

“我,24岁,年薪20万”:选对了行业究竟多重要?

那些在职场上顺风顺水&#xff0c;按部就班拿到高薪的人都有什么特点&#xff1f; 今天的主人公Flee告诉我&#xff0c;是稳。 在她的故事里&#xff0c;我看到一个“别人家的姑娘”&#xff0c;是怎样在职场上稳步晋升&#xff0c;大学毕业仅2年&#xff0c;就拿到18.6K月薪&a…

opencv-直方图均衡化

直方图均衡化是一种用于增强图像对比度的图像处理技术。它通过调整图像的灰度级别分布&#xff0c;使得图像中各个灰度级别的像素分布更均匀&#xff0c;从而提高图像的对比度。 在OpenCV中&#xff0c;你可以使用cv2.equalizeHist()函数来进行直方图均衡化。 以下是一个简单…

Flutter开发实践:用一套代码构建多端精美应用

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年6月CSDN上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师…