Finding group of columns with row sum equal one

Aha, That is a special case of a more general optimisation job I've spent many years on; I ended up with a very nice approach that is the opposite of brute force, and provides all solutions in one go.

Applied on your matrix situation, I'd like to describe it using boolean logic, i.e. all variables will have values 0 or 1, and the operators are AND (written as .), OR (written as +), and invert (written as /). Here we go:

call your columns A, B, C, D, ...
introduce variables a, b, c, d, indicating whether the corresponding column is or isn't used in the solution.

Now start building a, possibly huge, boolean expression TARGET, using the following pseudocode:

TARGET=1
foreach row {
    expr = some expression describing the row (explained below)
    TARGET = TARGET . expr
}
now reduce the TARGET expression using three facts:
step 1 = explode: x.(y+z) => x.y + x.z
step 2 = discard zeroes: x./x => 0
step 3 = power reduction: x.x => x

you can merge these steps (i.e. perform steps 2 and 3 while executing step 1), for clarity I will show them separately in the above order

what remains is the list of all solutions, pick any one of the terms and make it 1.
Depending on the matrix content, you will get zero, one or several solutions. 

Applied to your example:

a b c d
1 0 0 0
0 1 0 0
1 0 1 0
1 0 0 1

TARGET= 1        // for starters
.a               // row 1 says you need a
.b               // row 2 says you need b
.(a./c + /a.c)   // row 3 says you need either a or c but not both
.(a./d + /a.d)   // similar for row 4

exploded gives four terms as there are two groups of 2 terms in the expression:
TARGET=a.b.a./c.a./d + a.b./a.c.a./d + a.b.a./c./a.d + a.b./a.c./a.d

zero discarding will drop the last three products as they all contain a./a
power reduction of the remaining product yields:

TARGET=a.b./c./d

which means you must include A and B and must not include C and D.

For more complex problems, a typical final expression could be:

TARGET = a.b./c./d + a./b./c.d.e + /a.b.c./d.e

remarks:

1. when processing (inside the foreach loop) a row that holds N ones, you need N products; each product would have one positive column and N-1 inverted columns. So if there were a fifth row with "1 0 1 1" that would contribute (a./c./d + /a.c./d + /a./c.d)

2. when the final TARGET would hold S products, that indicates there are S solutions; any combination of variables that makes one product true or one, is a solution (no matter what the other products contribute).

3. when a product in the final TARGET does not hold all column variables, that means the missing columns are don't care, which in your application means those columns contain all zeroes.

4. if all-zero rows are present, you'll get TARGET = 0, so no solution.


So far the logic or mathematics. How you code this I'll leave up to you.