``````

In [1]:

from __future__ import print_function, division

from itertools import starmap, product

import numpy as np

``````
``````

In [2]:

def obtainable(coins):
"""Find the set of values obtainable with the given coins."""
combos = set(coins)
combos.update(map(sum, product(coins, coins)))
return combos

``````
``````

In [3]:

coins = [1, 2, 4]

``````
``````

In [4]:

obtainable(coins)

``````
``````

Out[4]:

{1, 2, 3, 4, 5, 6, 8}

``````
``````

In [5]:

values = set(range(1, 21))

def unobtainable(coins):
"""Find values that can't be obtained with the given coins."""
return values - obtainable(coins)

``````
``````

In [6]:

unobtainable(coins)

``````
``````

Out[6]:

{7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

``````
``````

In [7]:

def possible_new_coin(coins, value):
"""Generate new coins that would make the given value obtainable."""
if value % 2 == 0:
yield value // 2

for coin in coins:
if value > coin:
yield value - coin

``````
``````

In [8]:

set(possible_new_coin(coins, 7))

``````
``````

Out[8]:

{3, 5, 6}

``````
``````

In [9]:

set(possible_new_coin(coins, 9))

``````
``````

Out[9]:

{5, 7, 8}

``````
``````

In [10]:

set(possible_new_coin(coins, 10))

``````
``````

Out[10]:

{5, 6, 8, 9}

``````
``````

In [11]:

class Combinator:
def __init__(self, values):
self.values = values

combo = frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90})
self.combos = {combo}
self.smallest = len(combo)

"""Add a combo to the cache and update `smallest`."""
n = len(coins)
if n < self.smallest:
self.smallest = n

def unobtainable(self, coins):
"""Find values that can't be obtained with the given coins."""
return self.values - obtainable(coins)

def consider(self, coins):
"""Starting with `coins`, search for a minimal combo."""

# if we've already seen better, don't bother
if len(coins) > self.smallest:
return

# find unobtainable values

# if all values are obtainable, we're set
return

# otherwise, consider possible coins we could add
for new_coin in possible_new_coin(coins, value):
self.consider(coins | {new_coin})

def print_winners(self):
"""Print the best combinations."""
for combo in self.combos:
if len(combo) == self.smallest:
print(sorted(combo))

``````
``````

In [14]:

frozenset((1,))

``````
``````

Out[14]:

frozenset({1})

``````
``````

In [16]:

values = set(range(1, 21))
combinator = Combinator(values)
combinator.consider(frozenset((1,)))

``````
``````

In [17]:

combinator.smallest

``````
``````

Out[17]:

6

``````
``````

In [18]:

combinator.print_winners()

``````
``````

[1, 3, 5, 6, 13, 14]
[1, 3, 4, 8, 9, 11]
[1, 3, 5, 7, 9, 10]
[1, 3, 4, 9, 11, 16]
[1, 2, 5, 8, 9, 10]

``````
``````

In [ ]:

``````