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

Leetcode Day21组合总和

39 元素可重复选

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
可以重复选, 代表for j in range(start, n)中, 下一个dfs起点可以是j, 这样代表了重复选择, 但是如何保证不会死循环呢, 就需要利用都是正数的条件了

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:ans = []def dfs(path, partial_sum, start):if partial_sum > target:returnif partial_sum == target:ans.append(path[:])return for j in range(start, len(candidates)):path.append(candidates[j])dfs(path, partial_sum + candidates[j], j)path.pop()dfs([], 0, 0)return ans

39 nums中有重复, 但每个只能选一次

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

只用添加两个改变, 横向去重和下一个的开始index会变为j + 1

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:ans = []candidates.sort()def dfs(path, partial_sum, start):if partial_sum > target:returnif partial_sum == target:ans.append(path[:])returnfor j in range(start, len(candidates)):if j > start and candidates[j] == candidates[j - 1]:continuepath.append(candidates[j])dfs(path, partial_sum + candidates[j], j + 1)path.pop()dfs([], 0, 0)return ans

377

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [1] + [0] * targetfor i in range(1, len(dp)):for num in nums:if num > target:continuedp[i] += dp[i - num]return dp[-1]

http://www.mrgr.cn/news/19632.html

相关文章:

  • 鸿蒙正则校验无效 - Harmony
  • 如何使用 ef core 的 code first(fluent api)模式实现自定义类型转换器?
  • 开源网安引领AIGC+开发安全,智能防护铸就软件安全新高度
  • CCSI: 用于无数据类别增量学习的持续类别特定印象|文献速递--基于深度学习的医学影像病灶分割
  • VS按F11不进函数调试
  • 在线Ascii码对照表,Ascii转换对照表
  • gradle和maven相比有什么相同点和区别?
  • PIM
  • c++编程(24)——map的模拟实现
  • React、Vue.js 和 Angular主流前端框架介绍与选择指南
  • 如何在算家云搭建Qwen2(智能对话)
  • 模型从 HuggingFace 转存到 ModelScope
  • 蓝牙--关于bta_ag_rfc.cc文件的讲解
  • 项目日志——相关技术补充(1)
  • 【JVM】Java内存分配与回收:深入理解Java内存管理
  • el-table el-table-column表头嵌套循环数据
  • LLaMA-Factory仓基础功能架构及NPU/GPU环境实战演练
  • MySQL进阶篇3 -- 视图、存储过程、触发器
  • 海康二次开发笔记10-独立Group导入、导出及执行
  • 【MySQL】Ubuntu22.04安装MySQL8.0.39及修改默认用户名和密码