专栏首页算法与编程之美Python|回溯算法解决力扣排列组合2

Python|回溯算法解决力扣排列组合2

问题描述

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。解集不能包含重复的组合。

示例 1:

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

所求解集为:

[

[1,7],

[1,2, 5],

[2,6],

[1,1, 6]

]

解决方案

这道题的主要注意事项是一次组合中不能重复使用一个数字,与之区别开的另外一道题可参考力扣“组合总和1”题目。

这道题还是是一道较为基础的回溯算法题,根据回溯算法固有规律,我们可以将其看作是一种探索法。

先对candidates进行一个排序,创建一个result列表,储存得到的结果,用于最后输出。然后从第一个数开始尝试,回溯条件为当combination即当前相加和大于target时,就回到上一步;如果combination等于target,便存入result中并且继续回溯,直到结束。

这里值得注意的一个操作是剪枝,即不让元素被重复选取。

直接上代码:

for i in range(index,lenth-1): if i>index and candidates[i] == candidates[i-1]: continue

详细的更多剪枝细节可以深入探究。

Python代码:

def combinationSum2(candidates, target): result = [] candidates.sort() lenth = len(candidates) if lenth == 0: return [] def backtrack2(sums,index,combination): if sums > target: return if sums == target: result.append(combination) if sums < target: for i in range(index,lenth-1): if i>index and candidates[i] == candidates[i-1]: continue backtrack2(sums+candidates[i],i+1,combination+[candidates[i]]) backtrack2(0,-1,[]) return result

结语

回溯算法其实是一个架子,我们只需要根据题目的相应情况来调整回溯的条件与跳出的条件,相当于是套公式。只需要记住“公式”,理解算法思路,便可以用来轻松解题。

本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:李和龙

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python|力扣之组合总和2

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates ...

    算法与编程之美
  • 聊一聊编程中的函数

    给定一个数集A,假设其中的元素为x。现对A中的元素x施加对应法则f,记作f(x),得到另一数集B。假设B中的元素为y。则y与x之间的等量关系可以用y=f(x)表...

    算法与编程之美
  • 开发|Springboot文件上传与下载

    我们在做项目的时候很多时候会涉及到操作文件的步骤,今天我们就来讲讲如何实现Springboot文件上传与下载。

    算法与编程之美
  • Python|力扣之组合总和2

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates ...

    算法与编程之美
  • Spring Cloud构建微服务架构:服务容错保护(Hystrix断路器)【Dalston版】

    前言 在前两篇Spring Cloud构建微服务架构:服务容错保护(Hystrix服务降级)【Dalston版】和Spring Cloud构建微服务架构:服务容...

    程序猿DD
  • 8758:2的幂次方表示

    8758:2的幂次方表示 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 任何一个正整数都可以用2的幂次方表示。例如:  ...

    attack
  • SpringBoot里实现了某个接口的实现类运行时如何注入的?

    Candidates是在这个方法里解析出来的:protected Map<String, Object> findAutowireCandidates

    Jerry Wang
  • DSP图像处理

    最近着手把CSK移植到DSP中,先看一些DSP中图像处理的一些例子,第一件事当然就是怎么把图像数据倒入CCS工程中了,去年倒是用过一点CCS,再拿起来已经忘得差...

    和蔼的zhxing
  • 你是什么垃圾?五大机器人秒给答案,准确率95%!

    看点:垃圾分类机器人通过视觉系统分类垃圾,使用机械臂完成分拣,极大提高垃圾分拣效率。

    刀刀老高
  • 案例+解读,来自有道大神的17个常用Linux命令深度解析

    命令后带(Mac)标记的,表示该命令在Mac OSX下测试,其它的在Debian下测试。

    马哥linux运维

扫码关注云+社区

领取腾讯云代金券