[Python] Fastest way to find the least amount of subsets that sum up to the total set in Python

Say I have a dictionary of sets like this:

d = {'a': {1,2,8}, 'b': {3,1,2,6}, 'c': {0,4,1,2}, 'd': {9}, 'e': {2,5},
'f': {4,8}, 'g': {0,9}, 'h': {7,2,3}, 'i': {5,6,3}, 'j': {4,6,8}}


Each set represents a subset of a total set s = set(range(10)). I would like an efficient algorithm to find the least amount of keys that make up the whole set, and return an empty list if it's not possible by any combinations of keys. If there are many possible combinations that have the least amount of keys to sum up to the whole set, I only need one combination and it can be any one of those.

So far I am using an exhaustive approach that checks all possible combinations and then take the combination that has the least amount of keys.

import copy
def append_combinations(combo, keys):
for i in range(len(keys)):
new_combo = copy.copy(combo)
new_combo.append(keys)
new_keys = keys[i+1:]
if {n for k in new_combo for n in d[k]} == s:
valid_combos.append(new_combo)
append_combinations(new_combo, new_keys)

valid_combos = []
combo = []
keys = sorted(d.keys())
append_combinations(combo, keys)
sorted_combos = sorted(valid_combos, key=lambda x: len(x))
print(sorted_combos[0])
# ['a', 'c', 'd', 'h', 'i']


However, this becomes very expensive when the dictionary has many keys (in practice I will have around 100 keys). Any suggestions for a faster algorithm?

Continue reading...