Finding a subset of numbers that equals a single number

Question

Hi. First time user.

The reason I place this post is that I am looking to reconcile customer accounts receivable accounts where "payments" are posted to accounts instead of matched with the open invoices and cleared. So here is my issue:

Have a single number (payment) that should equal a subset of a given set of numbers (invoice amounts). Simple example:

Payment $10,002

Invoices values:

5001 2932 876 98 21 9923 2069 123 432 765

I would want a way to pull out 5001, 2932 and 2069 from this set.

Being a non-programmer, an Excel spreadsheet application is easiest for me to create. Ideas?

Answer 1

I worked on a very similar Java application that mapped receipts to accounts receivable transactions. We did not try to progammatically link summed receipts to a single transactions or vice-versa for a number of reasons. However, we did allow users to manually do that mapping. We just mapped receipt figures to transactions figures that matched, if there were multiple reciepts and transactions with the same amount, we only matched when there were the same number of duplicate amounts.

Answer 2

You're talking about an NP-Complete problem called Subset-sum.

Basically, this means that in general it is very computationally hard to compute the subset of prices that sums to your grand total. It is, however, very easy to check your answer since you merely sum your answers together.

My guess is, that if you want to examine N prices, you're going to have to use about 2^N cells in Excel to calculate this. The wikiepdia article linked above give some heuristics for approximating this.

Bottom line is, if you need to do this on a large scale (N is, say, in the thousands hundreds) you should rethink why you need to do this.

If you can find out a way to do it very efficiently, there may be a prize involved.