Use formula to find potential sum out of a group of numbers

[Tosborn]

Hey Mr. Excelers,

I work at a bank. Very often I need to find a variance (specified value) out of a large range of numbers. Say for example I have a bunch of transactions:

[TABLE="width: 87"]
<colgroup><col></colgroup><tbody>[TR]
[TD="align: right"]110.00
[/TD]
[/TR]
[TR]
[TD="align: right"]250.00
[/TD]
[/TR]
[TR]
[TD="align: right"]156,875.00
[/TD]
[/TR]
[TR]
[TD="align: right"]2.00[/TD]
[/TR]
[TR]
[TD="align: right"]5,566.27[/TD]
[/TR]
[TR]
[TD="align: right"]69.80[/TD]
[/TR]
[TR]
[TD="align: right"]15,000.00[/TD]
[/TR]
[TR]
[TD="align: right"]189,987.00[/TD]
[/TR]
[TR]
[TD="align: right"]58,999.00[/TD]
[/TR]
[TR]
[TD="align: right"]68.77[/TD]
[/TR]
</tbody>[/TABLE]

I need to find out if I can sum any of these numbers to get 249,054.77.

In this case it is easy as I know it is the last 3 numbers that add up to make 249,054.77. That is, 189,987.00 + 58,999.00 + 68.77 = 249,054.77. Therefore I can make 249,054.77 by a simple =sum(A8:A10)

However, when reconciling large accounts sometimes this list is much larger and it is often a large task to find out which of the number will equal our desired value. Is there a formula (possibly macro) that can tell me that the three numbers to make up 249,054.77 are located in cells A8, A9 & A10?

Many thanks,

Tim

 

[Tosborn]

182 numbers. But it crashes on some target values and not others. I just tried searching the target value that crashed the work computer again on my home computer (as it's faster than the work ones) and it took about 20 minutes, but it did work in the end. Pretty cool, maybe can try putting a progress bar in the macro?

Tim

 

[wideboydixon]

Would you care to help the OP to run the IOANNIS code also?

I have no idea how that works or what values need to be in which cells; the links give 404 errors.

WBD

 

[energman58]

The code here:

https://www.experts-exchange.com/questions/24793452/Matching-payments-against-open-invoices.html

In the mikeopolo reply is pretty fast but it is recursive so with 182 numbers it may take a while as you are doing an exhaustive search (in theory there are 2^182 possible combinations) it may help speed it up if you order the invoices largest to smallest first as that will eliminate infeasible solutions faster

 

[wideboydixon]

182 numbers. But it crashes on some target values and not others. I just tried searching the target value that crashed the work computer again on my home computer (as it's faster than the work ones) and it took about 20 minutes, but it did work in the end. Pretty cool, maybe can try putting a progress bar in the macro?

Tim

It's probably memory more than speed that makes the difference. Try to keep the search range down to a reasonable size

WBD

 

[wideboydixon]

The code here:

https://www.experts-exchange.com/questions/24793452/Matching-payments-against-open-invoices.html

In the mikeopolo reply is pretty fast but it is recursive so with 182 numbers it may take a while as you are doing an exhaustive search (in theory there are 2^182 possible combinations) it may help speed it up if you order the invoices largest to smallest first as that will eliminate infeasible solutions faster

That's practically identical to my algorithm but I didn't use recursion as I was trying to keep the memory footprint down to a reasonable size.

WBD

 

[Tosborn]

Yeah, it's the amount of numbers that's causing the issue. I can always break down the data into smaller batches and work it out like that. Considering 182^2 = [TABLE="width: 527"]
<colgroup><col width="527"></colgroup><tbody>[TR]
[TD="class: xl63, width: 527, align: right"]6,129,982,163,463,560,000,000,000,000,000,000,000,000,000,000,000,000,000.00
[/TD]
[/TR]
</tbody>[/TABLE]
half an hour processing time is pretty good!!

Either way it's an awesome macro. I showed it to my work colleague today, she was amazed!

Is it possible to put a progress bar in? Just so the user knows how far it is through.

Big thanks WBD, this is really cool!

Tim

 

[wideboydixon]

To show a progress bar would require implementing a user form. Besides, it's hard to say how far through it is because it optimises out some options.

I did think, however, that you might want to limit how many invoices are taken into consideration:

Book1
	A	B	C
1	110	362	Not Found
2	250	362	$A$1, $A$2, $A$4
3	156,875.00	362	$A$1, $A$2, $A$4
4	2
5	5,566.27
6	69.8
7	15,000.00
8	189,987.00
9	58,999.00
10	68.77
Sheet1

Cell Formulas
Range	Formula
C1	=FindTargetValue($A$1:$A$10,$B1,2)
C2	=FindTargetValue($A$1:$A$10,$B2,3)
C3	=FindTargetValue($A$1:$A$10,$B3)

Private counters() As Long
Public Function FindTargetValue(searchRange As Range, targetValue As Double, Optional maxValues) As String

Dim valueCount As Long
Dim maxLoop As Long

' Set the maximum size of the result set
maxLoop = searchRange.Count
If Not IsMissing(maxValues) Then maxLoop = CLng(maxValues)

' Set up the array only once
ReDim counters(maxLoop) As Long

' Look for combinations that add up to the total; start with 1!
For valueCount = 1 To maxLoop
    FindTargetValue = TryCombination(searchRange, targetValue, valueCount)
    If FindTargetValue <> "" Then Exit For
Next valueCount

' Default result
If FindTargetValue = "" Then FindTargetValue = "Not Found"

End Function
Private Function TryCombination(searchRange As Range, targetValue As Double, valueCount As Long) As String

Dim i As Long
Dim j As Long
Dim k As Long
Dim thisValue As Double
Dim statusUpdate As String

For i = 0 To valueCount - 1
    counters(i) = i + 1
Next i

Do
    ' Total for the current selection
    thisValue = 0
    
    ' Which counter we'll increment
    k = valueCount - 1
    
    ' Add up the totals for the current selection
    For i = 0 To valueCount - 1
        thisValue = thisValue + searchRange(counters(i)).Value
        
        ' No point continuing if we exceed the value early
        If Round(thisValue, 2) > Round(targetValue, 2) Then
            k = i
            Exit For
        End If
    Next i
    
    ' Check if we found a solution and, if so, return it
    If Round(thisValue, 2) = Round(targetValue, 2) Then
        TryCombination = searchRange(counters(0)).Address
        For i = 1 To valueCount - 1
            TryCombination = TryCombination & ", " & searchRange(counters(i)).Address
        Next i
        Exit Function
    End If
    
    ' Fetch the next combination
    i = k
    Do
        counters(i) = counters(i) + 1
        
        ' Have we exceeded the value for this counter?
        If counters(i) > searchRange.Count - (valueCount - 1 - i) Then
            ' Increment the previous one
            i = i - 1
        Else
            ' Set up subsequent counters
            For j = i + 1 To valueCount - 1
                counters(j) = counters(i) + j - i
            Next j
            
            ' Ready to test next combination
            Exit Do
        End If
    Loop Until i < 0
    
    ' If i < 0 then we've tested all possible combinations
Loop Until i < 0

End Function

 

[Tosborn]

Hey WBD,

FYI, tried that on a few sets of data but had some troubles sometimes finding a match.

Cheers,
Tim

 

[wideboydixon]

Hey WBD,

FYI, tried that on a few sets of data but had some troubles sometimes finding a match.

Cheers,
Tim

Oh.

Tricky for me to figure out why without having the data to hand.

WBD

 

[Tosborn]

Hey WBD,

Hahaa, sorry was just a bit busy and didn't do some proper testing.

Actually it's a good improvement. I didn't know you could just keep incrementing the 1,2,3 after the B1 (in the above example) until you get the match.

I used the rows trick to increment the number:

=FindTargetValue($A$1:$A$50,$B$1,ROWS($D$1:D5))

Works well! I found it was pretty efficient until the data set went above 60 transactions. But yeah, to be expected to have a lag on a big data set.

Thanks again,
Tim