leetcode39 -- Combination Sum

小郑之家~

题目


Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]



解答

combinationSumDFS(candidates, 6, 0, [2], [])

combinationSumDFS(candidates, -1, 1, [2,2,2,3], [[2,2,2,2]]) 但是这四个不对，所以直接返回,所以一直这样下去的话，就能把所有的都能够找到，这里有个很关键的地方即递归的时候传入的参数start是从i开始传入的，而不是i+1，这就意味着允许有重复的出现。

class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
self.combinationSumDFS(candidates, target, 0, [], res)
return res

def combinationSumDFS(self, candidates, target, start, out, res):
if target<0:
return
if target==0:
res.append(out[:])  # 注意这里append的是copy的,不然后面因为有删除操作的话,又都删除了.
return
for i in range(start, len(candidates)):
out.append(candidates[i])  # 把第一个元素拿起来之后，剩下的就是递归的子问题了，而且候选的元素不变，start也是从当前的这个元素i开始的。
self.combinationSumDFS(candidates, target-candidates[i], i, out, res)
del(out[-1])  # 递归完了之后无论candidates[i]合不合适都要把它去掉进行下一次的尝试。




class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
candidates.sort()
for i in range(len(candidates)):
if candidates[i]>target:
break
if candidates[i]==target:
res.append([candidates[i]])
break
later = candidates[i:]
temp = self.combinationSum(later, target-candidates[i])
# temp [[]]
for a in temp:
a.insert(0, candidates[i])
res.append(a)

return res