初学python记录:力扣39. 组合总和

article/2024/5/21 22:10:26

题目:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思考:

因为要找到所有和为target的组合,可以构建一棵树,根节点为target,每条路径的值为candidates中的数,路径连接的子节点即为 父节点-路径值 ,保证只有所有叶子节点的值为0(从根节点到叶子节点0的路径即为所求的一个组合)小于0(这条路径代表的组合不能满足和为target的条件)。以示例1为例,上述思路如下图所示:

可以看到找出了所有满足条件的组合,代码如下:

class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""n = len(candidates)ans = []candidates.sort()def makeTree(target, candidates, path, ans):if target < 0:returnelif target == 0:ans.append(path)returnelse:for index in range(0, n):makeTree(target - candidates[index], candidates, path + [candidates[index]], ans)makeTree(target, candidates, [], ans)return ans

但是可以看到结果中出现了顺序不同,但元素完全相同的组合,但题目中说明这种组合是同样的,不应该重复返回。在图中用绿色表示应该删去的分支:

 

可以总结出:每一层的第二个节点生成子节点的路径值不能使用生成他的前序兄弟节点的路径值。

这样就避免了重复组合的出现,代码如下:

class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""n = len(candidates)ans = []candidates.sort()def makeTree(target, candidates, path, ans, begin_index):if target < 0:returnelif target == 0:ans.append(path)returnelse:for index in range(begin_index, n):makeTree(target - candidates[index], candidates, path + [candidates[index]], ans, index)makeTree(target, candidates, [], ans, 0)return ans

提交通过:


http://www.ngui.cc/article/show-2038930.html

相关文章

three.js第一章(把three.js的官方文档下载到本地)

目录 打开three.js官网下载three.js打开本地three.js 打开three.js官网 three.js官网 下载three.js 1.进入gethub 点击版本号&#xff0c;进入gethub 2.下载three.js 点击下载 下载完之后&#xff0c;解压缩包&#xff0c; 进入文件&#xff0c;不要忘记 下载node_m…

探讨广播电视工程中无功补偿与谐波治理的办法

随着我国经济社会和科学技术的不断发展&#xff0c;新时期人们对于高品质生活的追求也在逐渐提高&#xff0c;特别是在文化追求方面&#xff0c;人们的需求日益多样&#xff0c;当前广播电视台发展过程中&#xff0c;由于相关的设备规模和数量不断增加&#xff0c;电视台工程的…

基于SpringBoot+Vue的物业管理系统 免费获取源码

项目源码获取方式放在文章末尾处 项目技术 数据库&#xff1a;Mysql5.7/8.0 数据表&#xff1a;28张 开发语言&#xff1a;Java(jdk1.8) 开发工具&#xff1a;idea 前端技术&#xff1a;vue 后端技术&#xff1a;SpringBoot 功能简介 项目获取关键字&#xff1a;物业…

DRF ModelSerializer序列化类

ModelSerializer序列化类 【0】准备 模型表创建 from django.db import modelsclass Book(models.Model):name models.CharField(max_length64, verbose_name书名)price models.DecimalField(max_digits6, decimal_places2, verbose_name价格)publish models.ForeignKey(…

(2024,时控交叉注意力(T-GATE),缓存和复用交叉注意力图)交叉注意力使文本到图像扩散模型的推理变得麻烦

Cross-Attention Makes Inference Cumbersome in Text-to-Image Diffusion Models 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 4. 交叉注意力的时间分析 4.1. 交叉注意力图…

中医药性笔记

当归 补血。 当归&#xff0c;腾讯医典

C++:map和set的使用

一、关联式容器介绍 在学习map和set之前&#xff0c;我们接触到的容器有&#xff1a;vector、list、stack、queue、priority_queue、array&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 关联式容器也是用…

鸿蒙入门09-CheckBox组件

参数 注意 &#xff1a; 配合 CheckBoxGroup 使用 参数形式 &#xff1a; Checkbox( options?: { name?: string, group?: string } ) 参数名 参数类型 是否必填 默认值 参数描述 name string 否 - 多选框名称 group string 否 - 多选框群组名称 属性 名称…

Day46代码随想录(1刷) 多重背包+动态规划

多重背包 多重背包就是物品数量不是只有一个也不是无限取而是有一个有限数量&#xff0c;我们可以把数量大过1的物品铺开也就是0-1背包问题了&#xff0c;所以多重背包可以转换成0-1背包 56. 携带矿石资源&#xff08;第八期模拟笔试&#xff09; 题目描述 你是一名宇航员&am…

mysql中连接两个字符串常量

如下代码&#xff1a; /// <summary>/// 获取需求集群分组集合/// </summary>/// <param name"cityCode"></param>/// <param name"indutrySubCode"></param>/// <returns></returns>public async Task&l…