Coin change problem with constraint: at most two coins in each denomination

106 Views Asked by At

I am studying recursive formulas in the famous coins problem in dynamic programming. However, I cannot solve this variation where there is a constraint where each coin (a power of two) could be used at most twice.

I know the recursive formula for the standard coin problem is as follows:

count[0]=1
def solve(x, coins):
    if (x<0): return 0
    else if x==0: return 1
    else:
        sum = 0 
        for c in coins:
            sum += solve(x-c)
        count[x]=sum
        return sum 

However, I am stuck at this constraint.

0

There are 0 best solutions below