Finding a subset which satisfies a certain condition

Question

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

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

I wish to find subsets such that, when the arrays are summed, the resulting array has individual elements which 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, v1+v2+v5 and v3+v6+v7 are suitable answers.

I have a brute force solution in mind, but I wanted to check if there is a more efficient method. Is this equivalent to the subset sum problem?

Answer 1

Do you want to find all solutions or one?

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

Represent each array as a binary number.

So v1 becomes 10011, v2 becomes 01001 etc.

Let * denote bitwise mod 2 addition.

e.g.

v1*v2*v3 = 00000

So our objective is to find arrays whose mod 2 addition is all zeroes. Let u and v be any binary number. Then u*v = 0 iff u = v.

e.g.

(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 from 0. Suppose 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 from T.

This is formally described below.

Each state is a binary number.

Let 0 be the initial state.

The given arrays are some subset of the state space, say S.

Our goal state is any element in S.

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

At each state let the possible actions be * with any state not in T.

After each action put the array used in T.

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

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