# Subset sum for lists [closed]

Given a target list

a = [2,4,1,4]


and a list of lists

b = [[0,0,0,1],
[2,1,0,0],
[1,0,1,1],
[1,4,0,3],
[5,2,5,2]]


how can I find a combination of lists that approximates the target list when added together?

E.g., in this case b + b + b is the optimal combination because it matches a.

• This is NP-hard; see set cover and exact cover. It is also not clear what you mean by "approximate"; that needs a formal definition. In any case, this does not appear to be a research-level question in theoretical CS, so it appears to be off-topic here.
– D.W.
Mar 12 at 18:42

Rephrasing in matrix form as I understand it, you would like to select the columns of a given matrix that add to the given "target" vector, which can be reduced to solving a linear system with binary variables, which can be written as an integer program (IP).

$$\begin{array}{ll} \underset{\mathrm x \in \mathbb Z^n}{\text{minimize}} & 0\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathbb 0_n \leq \mathrm x \leq \mathbb 1_n\end{array}$$

where $$m \times n$$ matrix $$\rm A$$ and $$m$$-vector $$\rm b$$ are given. In the example you gave, $$m=4$$ and $$n=5$$.

Using Python:

import cvxpy as cp
import numpy as np

A = np.array([( 0, 2, 1, 1, 5),
( 0, 1, 1, 4, 2),
( 0, 0, 1, 0, 5),
( 1, 0, 1, 3, 2)])

b = np.array([( 2),
( 5),
( 1),
( 5)])

# optimization variables
x = cp.Variable(5, integer=True)

# create optimization problem
prob = cp.Problem(cp.Minimize(0),
[ A @ x == b, np.zeros(5) <= x, x <= np.ones(5) ])

# solve optimization problem
solution = prob.solve()

print("Solution = ", x.value)


which outputs the following

Solution = [1. 0. 1. 1. 0.]


Thus, to obtain the "target" vector exactly, just add the 1st, 3rd and 4th columns, as you mentioned. If you want an approximation, you probably want to use Boolean least-squares.

• Thank you very much @Rodrigo. I confirm that the script works and it is what I was looking for, CVXPY looks very powerful indeed. However, the script returns Solution = None when the problem is infeasible. How can I get the closest solution to the target b? Mar 15 at 11:54
• @EnricMoreu To get the closest solution, try to remove the equality constraint and minimize the $1$-norm of the error vector via cp.minimize( norm(A @ x - b, 1) ). Let me know if this works (or not). Mar 15 at 16:39
• It worked like a charm. Thank you! Mar 16 at 19:07