def minElementSum2(n, S):
if n == 0:
return 0
if n < min(S):
return None
candidates = []
for s in S:
cand = minElementSum2( n-s, S )
if cand is not None:
candidates.append( cand + 1 )
if len(candidates) == 0:
return None
return min(candidates)
# def minElementSum(n, S):
# done = [None]*(n+1) # 0 through n inclusive
# done[0] = 0 # first is 0
# for i in range(n+1): # include n
# candidates = []
# for s in S:
# if i-s >= 0 and done[i-s] != None:
# candidates.append(done[i-s] + 1)
# if len(candidates) != 0:
# done[i] = min(candidates)
# # else, it stays as None
# return done[n]
done = [None]*101
done[0] = 0
def minElementSum3(n, S):
if done[n] != None:
return done[n]
else:
if n < min(S):
return None
candidates = []
for s in S:
cand = minElementSum3( n-s, S )
if cand is not None:
candidates.append( cand + 1 )
if len(candidates) == 0:
done[n] = None
else:
done[n] = min(candidates)
return done[n]
print(minElementSum2(20, [1, 2, 3, 4]))
print(minElementSum3(20, [1, 2, 3, 4]))
