Search for a subset satisfying a certain condition

Question

I have several arrays of numbers (each element of the array can only take the value 0 or 1), like this

  v1: 1;  0;  0;  one;  one; 
 v2: 0;  one;  0;  0;  one; 
 v3: 1;  one;  0;  one;  0; 
 v4: 1;  0;  0;  one;  0; 
 v5: 1;  one;  0;  one;  one; 
 v6: 1;  one;  0;  one;  one; 

I want to find such subsets that when summing arrays, the resulting array has separate elements that are multiples of 2. For example, v1 + v2 + v3 gives a resulting array of 2, 2, 0, 2, 2. The resulting array can have any value that is a multiple of 2.

Another example:

  v1: 1, 1, 1, 0, 1, 0
 v2: 0, 0, 1, 0, 0, 0
 v3: 1, 0, 0, 0, 0, 0
 v4: 0, 0, 0, 1, 0, 0
 v5: 1, 1, 0, 0, 1, 0
 v6: 0, 0, 1, 1, 0, 0
 v7: 1, 0, 1, 1, 0, 0

In this example, the answers v1 + v2 + v5 and v3 + v6 + v7 are suitable.

I have a solution for brute force, but I wanted to check if there is a more efficient method. Is this equivalent to the task of summing a subset?

Answer 1

Do you want to find all solutions or one?

This may find one solution (and I think it can be expanded to find all solutions).

We represent each array as a binary number.

So v1 becomes 10011, v2 becomes 01001, etc.

Let * denote the bitwise complement mod 2.

eg.

v1*v2*v3 = 00000 

So, our goal is to find arrays whose complement mod 2 is all zeros. Let u and v be any binary number. Then u * v = 0 if u = v.

eg.

 (v1*v2)*v3 = 0 v1*v2 = 11010 = v3. 

Also, if u * v = w, then

 u*v*v = w*v, so u*0 = w*v, u = w*v 

So, we can do a reverse search, starting at 0. Suppose that the final set of arrays contains v. Then v * T = 0, where T is some binary number. We have T = 0 * v. If T is one of the given arrays, then we are done. Otherwise, we continue the search starting with T.

This is formally described below.

Each state is a binary number.

Let 0 be the initial state.

These arrays are a subset of the state space, for example S.

Our goal state is any element in S.

Let T be the desired subset of arrays whose sum is 0.

In each state, let possible actions be * with any state not in T.

After each action, put the array used in T.

If S = T at any stage without a goal, then there is no solution.

Now we can run DFS in this space to find a solution.