In [4]:

    

from typing import Set


    

In [47]:

    

def is_coin_change_possible(xs: Set[int], v: int) -> int:
    # initialize all to false/0
    p = [0] * (v + 1)
    # base case
    p[0] = 1
    
    for i in range(1, v + 1):
        for x in xs:
            if x <= i:
                p[i] = max(p[i], p[i - x])
    # output 1 means change is possible and 0 means it's not
    return p[v]


    

In [44]:

    

is_coin_change_possible({5, 10}, 10)


    

    
Out[44]:





1

In [45]:

    

is_coin_change_possible({5, 10}, 12)


    

    
Out[45]:





0

In [46]:

    

is_coin_change_possible({5, 10}, 0)


    

    
Out[46]:





1

In [ ]: