算法-回溯算法-组合问题
77. 组合https://leetcode.cn/problems/combinations/
给定两个整数 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]]
class Solution {List<List<Integer>> ans=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return ans;}//start来记录下⼀层递归,搜索的起始位置。private void backtracking(int n,int k,int start){//遍历终止条件if(path.size()==k){ans.add(new ArrayList<>(path));return;}/**已经选择的元素path.size()还需要选择的元素k-path.size()*/for(int i=start;i<=n-(k-path.size())+1;i++){path.add(i);backtracking(n,k,i+1);path.remove(path.size()-1);}}
}
216. 组合总和 IIIhttps://leetcode.cn/problems/combination-sum-iii/description/
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
示例 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
没有其他符合的组合了。
class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum =0;public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k,n,1);return ans;}start来记录下⼀层递归,搜索的起始位置。private void backtracking(int k,int n,int start){//终止条件;组合大小=k或者和大于nif(path.size()==k||sum>n){if(sum==n){ans.add(new ArrayList<>(path));}return;}for(int i=start;i<=9-(k-path.size())+1;i++){path.add(i);sum+=i;backtracking(k,n,i+1);sum-=i;path.remove(path.size()-1);}}
}
39. 组合总和https://leetcode.cn/problems/combination-sum/description/
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum=0;public List<List<Integer>> combinationSum(int[] candidates, int target) {//排序是为了剪枝,如果加上当前元素已经大于target,那么就没有必要继续遍历下去Arrays.sort(candidates);backTracking(candidates, target, 0);return ans;}//start记录每层遍历的起始位置,元素可以无限制重复使用,因此start不需要变更private void backTracking(int[] candidates, int target, int start) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = start; i < candidates.length; i++) {//当前元素大于target终止遍历if(candidates[i]>target){break;}//元素之和大于target终止遍历if(sum+candidates[i]>target){continue;}sum += candidates[i];path.add(candidates[i]);backTracking(candidates, target, i);path.remove(path.size()-1);sum -= candidates[i];}}
}
40. 组合总和 IIhttps://leetcode.cn/problems/combination-sum-ii/description/
给定一个候选人编号的集合 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]
]
class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum=0;public List<List<Integer>> combinationSum2(int[] candidates, int target) {//记录每个元素使用boolean[] used = new boolean[candidates.length];Arrays.sort(candidates);backTracking(candidates, target,used, 0);return ans;}private void backTracking(int[] candidates, int target,boolean[] used,int start) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {//同层相同元素已经使用过则跳过if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1]==false) {continue;}used[i] = true;sum += candidates[i];path.add(candidates[i]);backTracking( candidates, target,used,i+1);path.remove(path.size()-1);sum -= candidates[i];used[i] = false;}}
}
相关文章:
算法-回溯算法-组合问题
77. 组合https://leetcode.cn/problems/combinations/ 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n 4, k 2 输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,…...
ABAP中的Null值与space 以及 BW中ADSO的Key值
写出来怪丢人,到现在还没搞懂这个。 在BW中创建ADSO,定义Key字段。可以看到ADSO表的定义中,所有的Key和Data属性如下: 所有的key会有关键字key打头,所有字段都有not null. 但是并不是有个字段是blank空的就不能更新进…...
JavaScript库之Lodash常用方法
Lodash 中文文档https://www.lodashjs.com/docs/lodash.omit/以下总结了在项目中常用的方法,其他的慢慢更新语言:cloneDeep这个方法类似_.clone,除了它会递归拷贝 value。(注:也叫深拷贝)参数value (*): 要…...
Kotlin新手教程二(Kotlin基本数据类型及基础语法)
一、基本数据类型 1.数字 由于Kotlin支持类型推断,所以在使用时若超出Int的范围则会被认定为其它类型;若需要显式指定Long型值,则需要在值后添加L后缀。 2.浮点数 3.比较两个数( 和 ) Kotlin 中没有基础数据类型&a…...
git idea创建新分支,获取/合并主支代码的2个方法
其他sql格式也在更新中,可直接查看这个系列,要是没有你需要的格式,可在评论或私信我 个人目录 获取主支代码的2个方法1,创建一个分支,获取主支的所有代码(场景:我需要一个自己的分支进行编写模…...
CF1714A Everyone Loves to Sleep 题解
CF1714A Everyone Loves to Sleep 题解题目链接字面描述题面翻译题目描述输入格式输出格式样例解释题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1代码实现题目 链接 https://www.luogu.com.cn/problem/CF1714A 字面描述 题面翻译 题目描述 Vlad和其他人一样&am…...
oracle官方下载历史版本JDK版本
背景 日常工作中由于一些特殊原因,我们需要下载指定系统指定位数指定版本的jdk,这个时候去网上搜索下载就会遇到各种坑,病毒、诱导连接、诱导关注/注册、付费、错误版本等,所以最好的办法是去官网下载,下面列举两种方式…...
双击-jar包无法运行解决方法
我自己是通过探索出来的方法解决的,网上的方法适合普通问题 网络流传方法 那种-jar和run.bat的就是曲解了问题意思,问题不是如何运行,而是如何双击jar包就可以直接运行。 普通小问题就是修改注册表,将java路径写进去后面加个 %1…...
程序员的自我修养第七章——动态链接 (下)
接上一篇。 7.3 地址无关代码 对于现代机器来说,引入地址无关代码并不麻烦,我们展示下各种模型的地址引用方式: 1. 模块内部函数调用 2. 模块内部的数据访问,如全局变量、静态变量。 3. 模块外部的函数调用,跳转。 4.…...
蓝桥杯刷题——基础篇(二)
这部分题目,主要面向有志参加ACM与蓝桥杯竞赛的同学而准备的,蓝桥杯与ACM考察内容甚至评测标准基本都一样,因此本训练计划提供完整的刷题顺序,循序渐进,提高代码量,巩固基础。因竞赛支持C语言、C、Java甚至…...
PTA L1-049 天梯赛座位分配(详解)
前言:内容包括:题目,代码实现,大致思路,代码解读 题目: 天梯赛每年有大量参赛队员,要保证同一所学校的所有队员都不能相邻,分配座位就成为一件比较麻烦的事情。为此我们制定如下策…...
Linux部分参数作用讲解
♥️作者:小刘在C站 ♥️个人主页:小刘主页 ♥️每天分享云计算网络运维课堂笔记,努力不一定有收获,但一定会有收获加油!一起努力,共赴美好人生! ♥️夕阳下,是最美的绽放࿰…...
Java kafka
JAVA面试题--Kafka(最新最全) 目录概述需求:设计思路实现思路分析1.URL管理2.网页下载器3.爬虫调度器4.网页解析器5.数据处理器拓展实现性能参数测试:参考资料和推荐阅读)Survive by day and develop by night. talk for import b…...
DBA之路---Stream数据共享同步机制与配置方法
oracle的Stream解析–数据共享 在g版本常用,如果是c版本项目一般都会选择goldengate,比stream靠谱多了 Oracle中的stream是消息队列一种应用形式,原理如下: 收集oracle中的事件,将事件保存在队列里,然后将…...
CF1790E Vlad and a Pair of Numbers 题解
CF1790E Vlad and a Pair of Numbers 题解题目链接字面描述题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1思路代码实现题目 链接 https://www.luogu.com.cn/problem/CF1790E 字面描述 题面翻译 共有 ttt 组数据。 每组数据你会得到一个正整数 xxx&…...
漏洞预警|Apache Kafka Connect JNDI注入漏洞
棱镜七彩安全预警 近日网上有关于开源项目Apache Kafka Connect JNDI注入漏洞,棱镜七彩威胁情报团队第一时间探测到,经分析研判,向全社会发起开源漏洞预警公告,提醒相关安全团队及时响应。 项目介绍 Karaf是Apache旗下的一个开…...
企业小程序开发步骤【教你创建小程序】
随着移动互联网的兴起,微信已经成为了很多企业和商家必备的平台,而其中,微信小程序是一个非常重要的工具。本文将为大家介绍小程序开发步骤,教你创建小程序。 步骤一、注册小程序账号 先准备一个小程序账号,在微信公…...
刚性电路板的特点及与柔性电路板的区别
打开市场上的任何一个电子产品,会发现里面都有一块或多块电路板。电路板是电子产品运行的核心,之前沐渥小编已经给大家介绍了柔性电路板,下面给大家介绍刚性电路板的基础知识。 刚性电路板俗称硬板,是由不容易变形的刚性基材制成的…...
扫码过磅+车牌识别,内蒙古蒙维过磅实现信息化管理
扫码过磅、车牌识别、对接SAP ERP系统设计思路: 无人值守系统升级改造包括车牌自动识别系统、信息化(扫码等方式)管理系统、智能自动控制系统等实现信息无纸化传递。远程监管地点设于公司东磅房,可以实现远程监测监控画面、称重过…...
蒙特卡洛计算圆周率
使用MC计算圆周率的小例子,使用python的numpy,matplotlib库import numpy as npimport matplotlib.pyplot as pltdef mc_calculate_pi(t):np.random.seed(t)rand_num np.random.rand(t)rand_num2 np.random.rand(t)l1 rand_num-0.5l2 rand_num2-0.5l0…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...
