3 ms·
I did the k = 0 case in an interview once (with nonempty subsets), and there's a neat little trick to do it in O(n).
by frankus 12y ago
I did the k = 0 case in an interview once (with nonempty subsets), and there's a neat little trick to do it in O(n).
- teraflop 12y agoEven with k=0, the problem is still NP-complete. Are you referring to the "pseudo-polynomial" trick where you maintain a bit vector of partial sums?
- frankus 12y agoNow that I think about it, it was a sequence of integers (looking for sub-sequences), not a set.
- repiret 12y agoTo be pendantic with terminology, if you take a sequence and remove some elements, what you're left with is a subsequence. If you take a sequence and you select some contiguous elements, what you get is a substring. So "amqz" is a subsequence of the alphabet but not a substring. "lmnop" is a substring and a subsequence.