Consider the following problem:

Set Cover

Input: A set I $=\{$i$1,$ i$2,...,$ in$\}$ of items and a set S $=\{$s$1,$ s$2,...,$ sm$\}$ of subsets of I.

Output: All minimum$-$size set covers of I, i$.$e$.,$ all smallest$-$possible size subsets S$\text{'}$ of S such that the union of all sets in S$\text{'}$ is equal to I.

Write and document a Python program that uses a recursive backtracking algorithm to print all minimum$-$size set covers for a given item$-$set I and item$-$subset set S$,$ where the files specifying I and S are input as command$-$line arguments. This algorithm will consider the set of candidate solutions consisting of all possible subsets of S$.$ An example item$-$subset set file iset$1.$txt is as follows:

$54$

$1$: $12$

$2$: $234$

$3$: $45$

$4$: $234$

Each such file of m item$-$subsets of a set of n items consists of n $+1$ lines, where the first line contains the integers n and m$,$ respectively, and the remaining lines contain the item$-$subsets, one per line, where each item$-$subset is specified by the number of the item$-$subset and its elements in ascending order. You may assume that all input files are formatted correctly. Examples of several program runs relative to the item$-$subset set files iset$1.$txt$,$ iset$2.$txt$,$ iset$3.$txt$,$ iset$4.$txt$,$ iset$5.$txt$,$ iset$6.$txt$,$ iset$7.$txt$,$ and iset$8.$txt are given in script file out.script.min. It is these results that your program should be able to replicate. To aid understanding how this program should work, you have also been provided with an expanded version of this script file which shows the program's progress through the search tree of candidate solutions.

Hints

You may find it convenient to determine the optimal solution cost and to print optimal solutions in two separate recursive procedures $($see sample Java code for solving the Vertex Cover described in Lecture #$1).$