Finding all possible combinations of row in a matrix where sum of columns represents a specific row vector

Question

ALGORITHM

One option is to turn this into the subset sum problem by choosing a base b and treating each row as a number in base b.

For example, with a base of 10 your initial problem turns into:

Consider the list of numbers
002 
110 
012 
112 
010 
212
Find all subsets that sum to 222

This problem is well known and is solvable via dynamic programming (see the wikipedia page).

If all your entries are nonnegative, then you can use David Psinger's linear time algorithm which has complexity O(nC) where C is the target number and n is the length of your list.

CHOICE OF BASE

The complexity of the algorithm is determined by the choice of the base b.

For the algorithm to be correct you need to choose the base larger than the sum of all the digits in each column. (This is needed to avoid solving the problem due to an overflow from one digit into the next.)

However, note that if you choose a smaller base you will still get all the correct solutions, plus some incorrect solutions. It may be worth considering using a smaller base (which will make the subset sum algorithm work much faster), followed by a postprocessing stage that checks all the solutions found and discards any incorrect ones.

Too small a base will produce an exponential number of incorrect solutions to discard, so the best size of base will depend on the details of your problem.

EXAMPLE CODE

Python code to implement this algorithm.

from collections import defaultdict

A=[ [0, 0, 2],
    [1, 1, 0],
    [0, 1, 2],
    [1, 1, 2],
    [0, 1, 0],
    [2, 1, 2] ]

target = [2,2,2]

b=10

def convert2num(a):
    t=0
    for d in a:
        t+=b*t+d
    return t

B = [convert2num(a) for a in A]

M=defaultdict(list)
for v,a in zip(B,A):
    M[v].append(a) # Store a reverse index to allow us to look up rows


# First build the DP array

# Map from number to set of previous numbers
DP = defaultdict(set)
DP[0] = set()
for v in B:
    for old_value in DP.keys():
        new_value = old_value+v
        if new_value<=target:
            DP[new_value].add(v)

# Then search for solutions
def go(goal,sol):
    if goal==0:
        # Double check
        assert map(sum,zip(*sol[:]))==target
        print sol
        return
    for v in DP[goal]:
        for a in M[v]:
            sol.append(a)
            go(goal-v,sol)
            sol.pop()

go(convert2num(target),[])

This code assumes that b has been chosen large enough to avoid overflow.