Woodstock Blog

a tech blog for general algorithmic interview questions

[Google] Set Cover Problem



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


“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"


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])


not written