0

I am trying to find an algorithm that solves this question but I am struggling.

Question: There are N subsets each has a cost of 1. (ex: 123, 145, 23, 12) We are trying to chose the minimum amount of subsets in order to have all digits of the subsets.

EX1: If the input 12 24 35 12345 13 14 15 23 25, the answer is 1 because we will only chose "12345".

CONSTRAINTS: The digits of the subset can be from 1 to 9 (zero is excluded), the number of subsets is always 9.

Brian61354270
  • 8,690
  • 4
  • 21
  • 43
den1z
  • 11
  • 1
  • 1
    This is known as the [set cover problem](https://en.wikipedia.org/wiki/Set_cover_problem). The first thing you need to do is figure out which digits are present in the subsets. This is easily done with a python `set` object. Add each digit of each subset to the `set`. Now you have the set that needs to be covered. Then try every possible combination of subsets. There are always 9 subsets, so there are only 2^9=512 possible combinations to try. The `itertools` package has a `combinations` method that will help with this. – user3386109 May 21 '21 at 20:51
  • 1
    Does this answer your question? [Any good implementation of greedy set cover for large datasets?](https://stackoverflow.com/questions/7936037/any-good-implementation-of-greedy-set-cover-for-large-datasets) – cigien May 22 '21 at 23:36

0 Answers0