# 377 combination sum iv

### 377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

Medium

class Solution(object):
def combinationSum4(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def combSum(candidates, target, start, valueList):
length = len(candidates)
if target == 0 :
res.append(valueList)
for i in range(start, length):
if target < candidates[i]:
return
combSum(candidates, target - candidates[i], 0, valueList + [candidates[i]])

candidates = list(set(candidates))
candidates.sort()
res = []
combSum(candidates, target, 0, [])
return len(res)


http://www.cnblogs.com/grandyang/p/5705750.html

AC代码

class Solution(object):
def combinationSum4(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
dp = [0 for i in range(target+1)]

dp[0] = 1

for i in range(target+1):
for candidate in candidates:
if i >= candidate:
dp[i] += dp[i - candidate]
return dp[-1]


apachecn/AiLearning