首页 > 代码库 > Leetcode 39. Combination Sum
Leetcode 39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7]
and target 7
,
A solution set is:
[ [7], [2, 2, 3] ]
一般跟求combiantion相关的题目基本上都会用到DFS。这里需要注意的是,用L22可以代替L23-L25。因为L22并没有改变 line, 所以line+[x]在内存中其实被另外的单独存储,所以不用line.pop()。
1 class Solution(object): 2 def combinationSum(self, candidates, target): 3 """ 4 :type candidates: List[int] 5 :type target: int 6 :rtype: List[List[int]] 7 """ 8 candidates.sort() 9 10 res = [] 11 line = [] 12 self.helper(candidates, target, res, line) 13 return res 14 15 def helper(self, candidates, target, res, line): 16 if target == 0: 17 res.append([x for x in line]) 18 return 19 20 for i, x in enumerate(candidates): 21 if x <= target: 22 # self.helper(candidates[i:], target-x, res, line+[x]) 23 line.append(x) 24 self.helper(candidates[i:], target-x, res, line) 25 line.pop() 26
Leetcode 39. Combination Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。