Find subset of integers that sum to a specific value

Question

I have a column in an Excel spreadsheet that is composed of positive and negative integers (credits and debits from an accounting ledger). I also have a specific value that is the sum of some subset of the integers from the aforementioned column. I want to find out which subset of these integers sum to produce this specific value in question.

In linear algebra terms, I interpret this problem as the following:

$$ \begin{bmatrix} a_1 & a_2 & a_3 & \ldots & a_n \end{bmatrix} \begin {bmatrix} x_1 \\ x_2 \\ \ldots \\ x_n \end{bmatrix} = y $$

where:

• $a_1,a_2,\ldots,a_n$ are integers (positive or negative)
• $x_1,x_2,\ldots,x_n$ are restricted to either $0$ or $1$
• $y$ is an integer

Is there a way to solve this programmatically? I am willing to try Wolfram Alpha, Excel tools, some Python script, or any other method. The best I can brainstorm at the moment is a Python script that loops through trying $2^n$ number of possibilities (0 or 1 for each $x_i$). There must be a better way, no?

Answer 1

This is the subset sum problem, and you can solve it via integer linear programming, with binary variables $x_i$ and linear constraint $\sum_{i=1}^n a_i x_i = y$.

Answer 2

This answer doesn't seem to belong to Math.SO, but here it goes in R (consider it an extended comment):

install.packages('utils')
require('utils')

set.seed(2)
(vec = unique(round(runif(10,-30, 30)))) # "positive and negative integers"
(x = sample(vec, 5, replace=F)) 
(S = sum(x)) # "a specific value that is the sum"

for(i in 1:length(vec)){
total.com = combn(vec, i, simplify = T)
if(sum(total.com[,which(colSums(total.com)==S)])!=0) print(total.com[,which(colSums(total.com)==S)])
}