python算法之组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[[7],[2,2,3]]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[ [2,2,2,2],[2,3,3],[3,5]]
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
if len(candidates) <= 0:
return res
candidates.sort()
self.dfs(candidates,[],target,0) # 递归回溯
return self.res
def dfs(self,candidates,sublist,target,last): # last表示当前sublist的最后一个元素
if target == 0:
self.res.append(sublist)
if target < candidates[0]: # 剪枝操作,目标值小于拥有的最小元素
return
for num in candidates: # 数字可重复使用,则每次从头遍历
if num > target: # 剪枝操作,当当前数值大于目标值,则后续无需遍历
return
if num < last: # 剪枝操作:若当前数值小于当前sublist的最后一个元素,则继续遍历,防止出现重复解决方案,如[2,2,3],[3,2,2]
continue
self.dfs(candidates,sublist+[num],target-num,num)
def t2(li,v):
li= sorted(li)
ans=[]
def f(s,use,remain): #s是li的坐标
for i in range(s,len(li)):
c=li[i]
if c==remain:
ans.append(use+[c])
if c<remain:
f(i,use+[c],remain-c)
if c>remain:
return
f(0,[],v)
return ans
if __name__ == '__main__':
li=[2,3,4,5,6,7]
r3=t2(li,10)
print(r3)
递归函数 dfs(candidates,sublist,target,last),其中sublist记录当前满足条件的子数组,last为当前子数组的最后一个元素。
剪枝操作1:目标值小于元素数组的最小元素,则无需继续遍历
剪枝操作2:当前元素大于目标值,则后续元素一定大于目标值(数组已排序),不会满足条件,无需继续遍历
剪枝操作3:若当前数值小于当前sublist的最后一个元素,则继续遍历,防止出现重复解决方案,如[2,2,3],[3,2,2]
相关文章
- 快速上手python的简单web框架flask
- 测试开发基础 | Python 算法与数据结构面试题系列一(附答案)
- 零基础学习python并成长为一名程序员,是否具有较大的难度
- python configParser配置文件模块
- 广度优先算法(BFS)、深度优先算法(DFS)、最短路径(dijkstra)的python代码实现
- python ftp 上传下载,创建不存在的目录
- Python——pip国内常用镜像
- 二叉树中的最大路径和-Python
- 高性能二分查找算法Python精简版
- python的笔记
- 《Python算法教程》——2.6 如果您感兴趣
- 《Python机器学习——预测分析核心算法》——2.6 多类别分类问题:它属于哪种玻璃
- 「基于Python技术的智慧中医商业项目」资讯数据&平台业务设计
- Python NVIDIA Isaac机器人平台开发教程之 02 Isaac Gym高性能GPU驱动算法集 实现端到端 GPU 加速物理模拟
- [python]打飞机小游戏代码
- 【Python分布式服务框架】python实现gRPC服务
- 使用Python中的urlparse、urllib抓取和解析网页(一)(转)
- TF-IDF的算法原理以及Python实现
- 华为OD机试 - 员工出勤(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 异常的打卡记录(Python) | 机试题+算法思路+考点+代码解析 【2023】
- python编程小技巧-切换工作目录到指定目录
- 推荐系统协同过滤-python实现(基于用户的协同过滤算法,基于物品的协同过滤算法,附数据集)
- Python 面向对象
- 2.1 The Python Interpreter(python解释器)
- 【图像处理】——Python实现图像加噪(随机噪声、椒盐噪声、高斯噪声等)