turn optimal_set_cover into a recursive program

from itertools import chain, combinations

def powerset(iterable):

s = list(iterable)

return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

def optimal_set_cover(universe, subsets, costs):

pset = powerset(subsets.keys())

best_set = None

best_cost = float("inf")

for subset in pset:

covered = set()

cost = 0

for s in subset:

covered.update(subsets[s])

cost += costs[s]

if len(covered) == len(universe) and cost < best_cost:

best_set = subset

best_cost = cost

return best_set

if __name__ == '__main__':

universe = {1, 2, 3, 4, 5}

subsets = {'S1': {4, 1, 3}, 'S2': {2, 5}, 'S3': {1, 4, 3, 2}}

costs = {'S1': 5, 'S2': 10, 'S3': 3}

optimal_cover = optimal_set_cover(universe, subsets, costs)

optimal_cost = sum(costs[s] for s in optimal_cover)

print('Optimal Set Cover:')

print(optimal_cover)

print('Cost = %s' % optimal_cost)