在一个集合(没有反复数字)中找到和为特定值的全部组合。
注意点:
样例:
输入: candidates = [2, 3, 6, 7], target = 7
输出: [[2, 2, 3], [7]]
採用回溯法。
因为组合中的数字要按序排列,我们先将集合中的数排序。依次把数字放入组合中,因为全部数都是正数,假设当前和已经超出目标值,则放弃。假设和为目标值。则添加结果集;假设和小于目标值。则继续添加元素。因为结果集中不同意出现反复的组合,所以添加元素时仅仅添加当前元素及之后的元素。
- class Solution(object):
- def combinationSum(self, candidates, target):
- """
- :type candidates: List[int]
- :type target: int
- :rtype: List[List[int]]
- """
- if not candidates:
- return []
- candidates.sort()
- result = []
- self.combination(candidates, target, [], result)
- return result
- def combination(self, candidates, target, current, result):
- s = sum(current) if current else 0
- if s > target:
- return
- elif s == target:
- result.append(current)
- return
- else:
- for i, v in enumerate(candidates):
- self.combination(candidates[i:], target, current + [v], result)
- if __name__ == "__main__":
- assert Solution().combinationSum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]
欢迎查看我的 Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
来源: http://www.bubuko.com/infodetail-2250969.html