10-13 LeetCode 39. Combination Sum
Description
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.
提供一个不包含重复数字的数字集合以及一个目标数。在集合中找出所有不同的组合使数字和等于目标数。
集合中的同一个数字可以重复使用任意次数
提示：
所有数字都是正数
集合不包含任何重复数字
例子：
given candidate set [2, 3, 6, 7] and target 7
集合为[2, 3, 6, 7]，目标数为7
则所有结果如下：
[
[2, 2, 3],
[7]
]
Solution 1:
像这种需要求出所有不同的组合的题目一般用递归来完成，似乎是叫回溯还是什么的一个算法。递归的尝试每一种组合，如果满足和等于目标值，则记下该组合，题目看起来好像已经解决了。但是我在写代码时遇到的最大的一个问题是，如何记录下每一个组合，最后发现也很简单，但确实卡了我一段时间，所以刷题的时候需要自己动手写一写，虽然题目看上去很简单，但是代码实现上还是有很多细节需要注意。
代码：
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.result = []
self.sum = target
candidates.sort()
self.get_sum(candidates, 0, 0, [])
return self.result
def get_sum(self, candidates, index, sum_now, lists):
if sum_now > self.sum:
return
elif sum_now == self.sum:
self.result.append(lists)
return
for i in range(index, len(candidates)):
self.get_sum(candidates, i, sum_now+candidates[i], lists+
[candidates[i]])
改进：
提交后运行速度不太理想，参考了下运行速度第一的代码，看完了觉得确实应该比我的要快一些，在递归的判断上有些区别，所以他的循环次数会比我的少一些，从而提高了运行速度，这些代码上的优化肯定需要长时间的多写多想。。
除此之外，他用来记录组合的方法是我做题时想到的第一个想法，只是我当时不知道如何实现。那个想法是只定义一个列表来保存组合，这个列表在递归的过程中不断变化，解释的不清楚，直接上代码。
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not candidates or not target:
return []
candidates.sort()
self.res = []
self.dfs(candidates, 0, target, [])
return self.res
def dfs(self, candidates, start, remain_target, ans):
if remain_target == 0:
self.res.append(ans[:])
return
for i in xrange(start, len(candidates)):
if candidates[i] > remain_target:
break
ans.append(candidates[i])
self.dfs(candidates, i, remain_target - candidates[i], ans)
del ans[-1]
感想
今天的题目不难，但是发现了另外的一个问题：语言表达能力不够。会写与能解释给别人听是两个境界吧,看到题目以后觉得就是那样写就可以了，但是解释的时候却解释不出来那样是哪样。。。继续努力吧。。。。。。。。。。。
