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.
提供一個不包含重復(fù)數(shù)字的數(shù)字集合以及一個目標(biāo)數(shù)绞绒。在集合中找出所有不同的組合使數(shù)字和等于目標(biāo)數(shù)垄分。
集合中的同一個數(shù)字可以重復(fù)使用任意次數(shù)
提示：
所有數(shù)字都是正數(shù)
集合不包含任何重復(fù)數(shù)字
例子：
given candidate set [2, 3, 6, 7] and target 7
集合為[2, 3, 6, 7]，目標(biāo)數(shù)為7
則所有結(jié)果如下：
[
[2, 2, 3],
[7]
]
Solution 1:
像這種需要求出所有不同的組合的題目一般用遞歸來完成悲敷，似乎是叫回溯還是什么的一個算法弃理。遞歸的嘗試每一種組合魔种，如果滿足和等于目標(biāo)值状答，則記下該組合，題目看起來好像已經(jīng)解決了咱揍。但是我在寫代碼時遇到的最大的一個問題是泌霍，如何記錄下每一個組合，最后發(fā)現(xiàn)也很簡單述召，但確實卡了我一段時間，所以刷題的時候需要自己動手寫一寫蟹地，雖然題目看上去很簡單积暖，但是代碼實現(xiàn)上還是有很多細(xì)節(jié)需要注意。
代碼：
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]])
改進(jìn)：
提交后運行速度不太理想怪与，參考了下運行速度第一的代碼夺刑，看完了覺得確實應(yīng)該比我的要快一些，在遞歸的判斷上有些區(qū)別分别，所以他的循環(huán)次數(shù)會比我的少一些遍愿，從而提高了運行速度，這些代碼上的優(yōu)化肯定需要長時間的多寫多想耘斩。沼填。
除此之外，他用來記錄組合的方法是我做題時想到的第一個想法括授，只是我當(dāng)時不知道如何實現(xiàn)坞笙。那個想法是只定義一個列表來保存組合岩饼，這個列表在遞歸的過程中不斷變化，解釋的不清楚薛夜，直接上代碼籍茧。
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]
感想
今天的題目不難，但是發(fā)現(xiàn)了另外的一個問題：語言表達(dá)能力不夠梯澜。會寫與能解釋給別人聽是兩個境界吧,看到題目以后覺得就是那樣寫就可以了寞冯，但是解釋的時候卻解釋不出來那樣是哪樣。晚伙。吮龄。繼續(xù)努力吧。撬腾。螟蝙。。民傻。胰默。。漓踢。牵署。。喧半。
