find sum in list of of numbers

I am with you on the brute force requirement, but there are a couple of
tricks to minimize the permiutations and combinations. By sorting the list of
input values you can determine to stop testing certain combinations knowing
that certain solutions can not be possible because they are going to be too
large. That is where the code that I posted is very good. I had some other
code that did almost exactly what you were suggesting but it was far slower.
From what I have seen Harlan's code is hard to beat. That being said the list
you are searching should be at most 25 or 30 entries.
--
HTH...

Jim Thomlinson


"Bill Martin" wrote:

wrote:
Hello,

I have a list of numbers in a column and I need to find which numbers
when summed together equal a figure. I have a list of invoice amounts
that I need to match up with payments (the payments are always made for
several invoices so I need to come up with sums of several invoices to
get to this payment amount).

An example would be I have this in the following section (A1:A10):
$17,213.82
$4,563.02
$85,693.42
$1,166.01
$725.90
$580.09
$2,243.75
$240.16
$207.70
$725.90

I need to find which combination of these figures would sum $1,173.76.

Thanks in Advance,
Dza the troubled accountant


-----------------------------------

I don't believe there is a simple, closed form solution to this problem. What
you have to do is to exhaustively try all possible combinations to see which one
(or *ones*) add up to what you want. This is possible to do with small problems
like the example you've shown, but if there are a "large" number of entries it
will take computer time in excess of the age of the universe to calculate. With
100 entries for example, the number of combinations you'd have to test 1.27
times ten to the 30th power -- a *really* big number. With 20 entries you'd
"only" have about one million combinations to check.

What I would do is add an extra column of only 0 and 1 vales which represents a
binary word in aggregate. Then multiply that column by your dollar values and
sum them. This gives you the what that particular combination adds up to. Then
you need to increment the binary word by one and do it again ... and again.
Until you've tested all combinations.

You're going to need a VBA macro to make this work. I don't think you can do it
with simple formulas.

Good luck...

Bill

You're right, Jim, the OP could reduce his solution space by
disregarding the numbers greater than his "target" number. In an
accounting environment, however, debits and credits (positive as well
as negative) may need to be considered- the negative numbers may react
with the positive larger numbers to arrive at the correct solution.

I do agree that Harlan's code looks good. I haven't tried to compile and run
it, but it looks like a good approach.

Bill
------------------------------
Jim Thomlinson wrote:
I am with you on the brute force requirement, but there are a couple of
tricks to minimize the permiutations and combinations. By sorting the list of
input values you can determine to stop testing certain combinations knowing
that certain solutions can not be possible because they are going to be too
large. That is where the code that I posted is very good. I had some other
code that did almost exactly what you were suggesting but it was far slower.
From what I have seen Harlan's code is hard to beat. That being said the list
you are searching should be at most 25 or 30 entries.

Use Google's group search: http://groups.google.com/advanced_group_search

, look in Groups *excel*, with all of the words Add up numbers, Author
Harlan (yes, indeed, Harlan Grove)
and you'll find a discussion and very advanced solutions about this subject

--
Kind regards,

Niek Otten

"Dave O" wrote in message
ups.com...
You're right, Jim, the OP could reduce his solution space by
disregarding the numbers greater than his "target" number. In an
accounting environment, however, debits and credits (positive as well
as negative) may need to be considered- the negative numbers may react
with the positive larger numbers to arrive at the correct solution.

Sorry, I missed that it had already been mentioned here

--
Kind regards,

Niek Otten

"Niek Otten" wrote in message
...
Use Google's group search:
http://groups.google.com/advanced_group_search

, look in Groups *excel*, with all of the words Add up numbers, Author
Harlan (yes, indeed, Harlan Grove)
and you'll find a discussion and very advanced solutions about this
subject

--
Kind regards,

Niek Otten

"Dave O" wrote in message
ups.com...
You're right, Jim, the OP could reduce his solution space by
disregarding the numbers greater than his "target" number. In an
accounting environment, however, debits and credits (positive as well
as negative) may need to be considered- the negative numbers may react
with the positive larger numbers to arrive at the correct solution.

That is not quite what the code does. What it does is it sorts the original
values lowest to highest. Negatives will obviously be the lowest values. When
it is doing the combinations it moves in the direction of adding the next
highest number. If the combination exceeds the target value then it abandons
moving to the following next highest value because it obviously is not a
possible solution. I am not sure that I explained that very well but sufice
it to say that it works and it speeds up the execution by potentially a few
orders of magnitude.
--
HTH...

Jim Thomlinson


"Dave O" wrote:

You're right, Jim, the OP could reduce his solution space by
disregarding the numbers greater than his "target" number. In an
accounting environment, however, debits and credits (positive as well
as negative) may need to be considered- the negative numbers may react
with the positive larger numbers to arrive at the correct solution.