# input: a[0..N) array of distinct positive integers, N>=0, and S# output: number of ways that S can be obtained with an unlimited# amount of coins with denominations in a[0..N)## exponential (in N) naive solutiondefcc_naive(a,S):returncc_aux(a,len(a),S)defcc_aux(a,n,s):ans=Noneifn==0:ans=1ifs==0else0else:ans=cc_aux(a,n-1,s)ifa[n-1]<=s:ans+=cc_aux(a,n,s-a[n-1])returnans
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.