leetcode 40. 组合总和 II (python)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 40. 组合总和 II (python),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1230字,纯文字阅读大概需要2分钟。
内容图文
![leetcode 40. 组合总和 II (python)](/upload/InfoBanner/zyjiaocheng/739/f6e19ec7128e41839f9b41ea4bdb2537.jpg)
给定一个数组 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]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: if len(candidates)<=0: return [] candidates.sort() self.res = [] self.dfs(candidates,[],target,0) return self.res def dfs(self,candidates,sublist,target,index): if target == 0: self.res.append(sublist) return if target < 0: return for i in range(index,len(candidates)): # 从当前index开始遍历 if i != index and candidates[i] == candidates[i-1]: # 保证每个数字只使用一次 continue self.dfs(candidates,sublist+[candidates[i]],target-candidates[i],i+1)
参考链接: https://blog.csdn.net/weixin_40546602/article/details/88357837
回溯递归函数dfs(self,candidates,sublist,target,index),index为当前遍历到数组的位置,因为不允许重复使用元素,只可依次遍历。
剪枝操作1: 当target值已经小于0,由于数组中包含负数,所有之间返回
剪枝操作2:保证每个数字只使用一次
内容总结
以上是互联网集市为您收集整理的leetcode 40. 组合总和 II (python)全部内容,希望文章能够帮你解决leetcode 40. 组合总和 II (python)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。