[Solved]: Subset sum-like problem over boolean vectors

Problem Detail: 

I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

Say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on Wikipedia (modifying it to store maximal sets of subsets rather than true/false): Pseudo-polynomial time dynamic programming solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

Asked By : Jake

Answered By : Yuval Filmus

Let us say that $x \leq y$ if $x_i \leq y_i$ for all $i$. Suppose that your starting vectors are $x_1,\ldots,x_n$ and your target is $y$. If $x_i \not\leq y$ then $x_i$ cannot belong to any solution, so you can throw away all these vectors. The remaining vectors OR together to a vector $x \leq y$. If $x \neq y$ then there is no solution. Otherwise, take all remaining vectors – this is clearly the maximal solution.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61127

3.2K people like this

 Download Related Notes/Documents