### Question

Give a list of documents, find the minimal document set that can cover all the characters in all the documents.

eg.

```
“a b c h j”,
"c d”,
“a b c”
“a f g”
“a h j”
```

The result should be

```
"a b c h j"
"c d" and
"a f g"
```

### Solution

Set cover problem is NP.

**DP solution is available** here, with O(2 ^ n) time complexity.

T[i][X] denotes the minimal number of sets out of {S1, S2, … , Si} that covers X.

So we have:

T[i][X] = min(1 + T[i − 1][X - Si], T[i − 1][X])

### Code

not written