I have a long list of monetary amounts listed on an excel spreadsheet. I am
trying to find combinations of those amounts that add up to certain larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or function
I can use on a large scale for this type of thing?

You can use solver,

there was a similar question a few days ago, here's a link

http://tinyurl.com/pfswm


note that the solver that comes with excel is limited in how large data set
you can use


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com



"Joshua Jacoby" wrote in message
...
I have a long list of monetary amounts listed on an excel spreadsheet. I
am
trying to find combinations of those amounts that add up to certain larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or
function
I can use on a large scale for this type of thing?

Interesting question

You could do this by using the DEC2BIN function to generate all of the
binary numbers up to two to the power of the count of the numbers that
you have. The individual places could then be used as switches for
whether each number is included in the sum or not. This would allow you
to evaluate all possible combinations and therefore see which matches
your target.


--
mrice

Research Scientist with many years of spreadsheet development experience
------------------------------------------------------------------------
mrice's Profile: http://www.excelforum.com/member.php...o&userid=10931
View this thread: http://www.excelforum.com/showthread...hreadid=540388

Hmm, I just tried that link and I was denied access to it by my work pc.

"Peo Sjoblom" wrote:

You can use solver,

there was a similar question a few days ago, here's a link

http://tinyurl.com/pfswm


note that the solver that comes with excel is limited in how large data set
you can use


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com



"Joshua Jacoby" wrote in message
...
I have a long list of monetary amounts listed on an excel spreadsheet. I
am
trying to find combinations of those amounts that add up to certain larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or
function
I can use on a large scale for this type of thing?

Hmm, well here's the situation. I'm trying to reconcile an account that has
over 300 entries in it for the month of december. So, over 300 debits, but
only say 100 credits. And I'm trying to each credit with the corresponding
bunch of debits. It takes forever to try to do it visually by highlighting
groups of debit entries to match their sum to a credit entry. You understand
what I mean?

"mrice" wrote:


Interesting question

You could do this by using the DEC2BIN function to generate all of the
binary numbers up to two to the power of the count of the numbers that
you have. The individual places could then be used as switches for
whether each number is included in the sum or not. This would allow you
to evaluate all possible combinations and therefore see which matches
your target.


--
mrice

Research Scientist with many years of spreadsheet development experience
------------------------------------------------------------------------
mrice's Profile: http://www.excelforum.com/member.php...o&userid=10931
View this thread: http://www.excelforum.com/showthread...hreadid=540388

This code by Harlan Grove may help (I haven't tried it myself!). It finds
numbers that add to a given sum.

'Begin VBA Code


' By Harlan Grove


Sub findsums()
'This *REQUIRES* VBAProject references to
'Microsoft Scripting Runtime
'Microsoft VBScript Regular Expressions 1.0 or higher


Const TOL As Double = 0.000001 'modify as needed
Dim c As Variant


Dim j As Long, k As Long, n As Long, p As Boolean
Dim s As String, t As Double, u As Double
Dim v As Variant, x As Variant, y As Variant
Dim dc1 As New Dictionary, dc2 As New Dictionary
Dim dcn As Dictionary, dco As Dictionary
Dim re As New RegExp


re.Global = True
re.IgnoreCase = True


On Error Resume Next


Set x = Application.InputBox( _
Prompt:="Enter range of values:", _
Title:="findsums", _
Default:="", _
Type:=8 _
)


If x Is Nothing Then
Err.Clear
Exit Sub
End If


y = Application.InputBox( _
Prompt:="Enter target value:", _
Title:="findsums", _
Default:="", _
Type:=1 _
)


If VarType(y) = vbBoolean Then
Exit Sub
Else
t = y
End If


On Error GoTo 0


Set dco = dc1
Set dcn = dc2


Call recsoln


For Each y In x.Value2
If VarType(y) = vbDouble Then
If Abs(t - y) < TOL Then
recsoln "+" & Format(y)


ElseIf dco.Exists(y) Then
dco(y) = dco(y) + 1


ElseIf y < t - TOL Then
dco.Add Key:=y, Item:=1


c = CDec(c + 1)
Application.StatusBar = "[1] " & Format(c)


End If


End If
Next y


n = dco.Count


ReDim v(1 To n, 1 To 3)


For k = 1 To n
v(k, 1) = dco.Keys(k - 1)
v(k, 2) = dco.Items(k - 1)
Next k


qsortd v, 1, n


For k = n To 1 Step -1
v(k, 3) = v(k, 1) * v(k, 2) + v(IIf(k = n, n, k + 1), 3)
If v(k, 3) t Then dcn.Add Key:="+" & _
Format(v(k, 1)), Item:=v(k, 1)
Next k


On Error GoTo CleanUp
Application.EnableEvents = False
Application.Calculation = xlCalculationManual


For k = 2 To n
dco.RemoveAll
swapo dco, dcn


For Each y In dco.Keys
p = False


For j = 1 To n
If v(j, 3) < t - dco(y) - TOL Then Exit For
x = v(j, 1)
s = "+" & Format(x)
If Right(y, Len(s)) = s Then p = True
If p Then
re.Pattern = "\" & s & "(?=(\+|$))"
If re.Execute(y).Count < v(j, 2) Then
u = dco(y) + x
If Abs(t - u) < TOL Then
recsoln y & s
ElseIf u < t - TOL Then
dcn.Add Key:=y & s, Item:=u
c = CDec(c + 1)
Application.StatusBar = "[" & Format(k) & "] " & _
Format(c)
End If
End If
End If
Next j
Next y


If dcn.Count = 0 Then Exit For
Next k


If (recsoln() = 0) Then _
MsgBox Prompt:="all combinations exhausted", _
Title:="No Solution"


CleanUp:
Application.EnableEvents = True
Application.Calculation = xlCalculationAutomatic
Application.StatusBar = False


End Sub


Private Function recsoln(Optional s As String)
Const OUTPUTWSN As String = "findsums solutions" 'modify to taste


Static r As Range
Dim ws As Worksheet


If s = "" And r Is Nothing Then
On Error Resume Next
Set ws = ActiveWorkbook.Worksheets(OUTPUTWSN)
If ws Is Nothing Then
Err.Clear
Application.ScreenUpdating = False
Set ws = ActiveSheet
Set r = Worksheets.Add.Range("A1")
r.Parent.Name = OUTPUTWSN
ws.Activate
Application.ScreenUpdating = False
Else
ws.Cells.Clear
Set r = ws.Range("A1")
End If
recsoln = 0
ElseIf s = "" Then
recsoln = r.Row - 1
Set r = Nothing
Else
r.Value = s
Set r = r.Offset(1, 0)
recsoln = r.Row - 1
End If
End Function


Private Sub qsortd(v As Variant, lft As Long, rgt As Long)
'ad hoc quicksort subroutine
'translated from Aho, Weinberger & Kernighan,
'"The Awk Programming Language", page 161


Dim j As Long, pvt As Long


If (lft = rgt) Then Exit Sub
swap2 v, lft, lft + Int((rgt - lft + 1) * Rnd)
pvt = lft
For j = lft + 1 To rgt
If v(j, 1) v(lft, 1) Then
pvt = pvt + 1
swap2 v, pvt, j
End If
Next j


swap2 v, lft, pvt


qsortd v, lft, pvt - 1
qsortd v, pvt + 1, rgt
End Sub


Private Sub swap2(v As Variant, i As Long, j As Long)
'modified version of the swap procedure from
'translated from Aho, Weinberger & Kernighan,
'"The Awk Programming Language", page 161


Dim t As Variant, k As Long


For k = LBound(v, 2) To UBound(v, 2)
t = v(i, k)
v(i, k) = v(j, k)
v(j, k) = t
Next k
End Sub


Private Sub swapo(a As Object, b As Object)
Dim t As Object


Set t = a
Set a = b
Set b = t
End Sub
'---- end VBA code ----




"Joshua Jacoby" wrote:

Hmm, well here's the situation. I'm trying to reconcile an account that has
over 300 entries in it for the month of december. So, over 300 debits, but
only say 100 credits. And I'm trying to each credit with the corresponding
bunch of debits. It takes forever to try to do it visually by highlighting
groups of debit entries to match their sum to a credit entry. You understand
what I mean?

"mrice" wrote:


Interesting question

You could do this by using the DEC2BIN function to generate all of the
binary numbers up to two to the power of the count of the numbers that
you have. The individual places could then be used as switches for
whether each number is included in the sum or not. This would allow you
to evaluate all possible combinations and therefore see which matches
your target.


--
mrice

Research Scientist with many years of spreadsheet development experience
------------------------------------------------------------------------
mrice's Profile: http://www.excelforum.com/member.php...o&userid=10931
View this thread: http://www.excelforum.com/showthread...hreadid=540388

Here it is, this example was done on a small data set but you should be able
to use this technique, instead of 8 in this example you would put the first
credit than use the debits in let's say A2:A308, B2:B308 would have 1s and
so on

"put the data set in let's say A2:A8, in B2:B8 put a set of ones {1,1,1 etc}
in the adjacent cells
in C2 put 8, in D2 put


=SUMPRODUCT(A2:A7,B2:B7)


select D2 and do toolssolver, set target cell $D$2 (should come up
automatically if selected)


Equal to a Value of 8, by changing cells $B$2:$B$7, click add under Subject
to the constraints of:
in Cell reference put


$B$2:$B$7


from dropdown select Bin, click OK and click Solve, Keep solver solution
and look at the table


2 1
4 0
5 0
6 1
9 0
13 0


there you can see that 4 ones have been replaced by zeros and the adjacent
cells to the 2 ones total 8 "


adapt to fit"


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com


"Joshua Jacoby" wrote in message
...
Hmm, I just tried that link and I was denied access to it by my work pc.

"Peo Sjoblom" wrote:

You can use solver,

there was a similar question a few days ago, here's a link

http://tinyurl.com/pfswm


note that the solver that comes with excel is limited in how large data
set
you can use


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com



"Joshua Jacoby" wrote in message
...
I have a long list of monetary amounts listed on an excel spreadsheet.
I
am
trying to find combinations of those amounts that add up to certain
larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or
function
I can use on a large scale for this type of thing?

Thank you Peo. Uggghh, I don't think my version has solver. it's not listed
under tools... Well, I guess I can't do it.

"Peo Sjoblom" wrote:

Here it is, this example was done on a small data set but you should be able
to use this technique, instead of 8 in this example you would put the first
credit than use the debits in let's say A2:A308, B2:B308 would have 1s and
so on

"put the data set in let's say A2:A8, in B2:B8 put a set of ones {1,1,1 etc}
in the adjacent cells
in C2 put 8, in D2 put


=SUMPRODUCT(A2:A7,B2:B7)


select D2 and do toolssolver, set target cell $D$2 (should come up
automatically if selected)


Equal to a Value of 8, by changing cells $B$2:$B$7, click add under Subject
to the constraints of:
in Cell reference put


$B$2:$B$7


from dropdown select Bin, click OK and click Solve, Keep solver solution
and look at the table


2 1
4 0
5 0
6 1
9 0
13 0


there you can see that 4 ones have been replaced by zeros and the adjacent
cells to the 2 ones total 8 "


adapt to fit"


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com


"Joshua Jacoby" wrote in message
...
Hmm, I just tried that link and I was denied access to it by my work pc.

"Peo Sjoblom" wrote:

You can use solver,

there was a similar question a few days ago, here's a link

http://tinyurl.com/pfswm


note that the solver that comes with excel is limited in how large data
set
you can use


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com



"Joshua Jacoby" wrote in message
...
I have a long list of monetary amounts listed on an excel spreadsheet.
I
am
trying to find combinations of those amounts that add up to certain
larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or
function
I can use on a large scale for this type of thing?

Wow, that's a long code. Where am I supposed to put that? I don't
understand any of it.

"Toppers" wrote:


This code by Harlan Grove may help (I haven't tried it myself!). It finds
numbers that add to a given sum.

'Begin VBA Code


' By Harlan Grove


Sub findsums()
'This *REQUIRES* VBAProject references to
'Microsoft Scripting Runtime
'Microsoft VBScript Regular Expressions 1.0 or higher


Const TOL As Double = 0.000001 'modify as needed
Dim c As Variant


Dim j As Long, k As Long, n As Long, p As Boolean
Dim s As String, t As Double, u As Double
Dim v As Variant, x As Variant, y As Variant
Dim dc1 As New Dictionary, dc2 As New Dictionary
Dim dcn As Dictionary, dco As Dictionary
Dim re As New RegExp


re.Global = True
re.IgnoreCase = True


On Error Resume Next


Set x = Application.InputBox( _
Prompt:="Enter range of values:", _
Title:="findsums", _
Default:="", _
Type:=8 _
)


If x Is Nothing Then
Err.Clear
Exit Sub
End If


y = Application.InputBox( _
Prompt:="Enter target value:", _
Title:="findsums", _
Default:="", _
Type:=1 _
)


If VarType(y) = vbBoolean Then
Exit Sub
Else
t = y
End If


On Error GoTo 0


Set dco = dc1
Set dcn = dc2


Call recsoln


For Each y In x.Value2
If VarType(y) = vbDouble Then
If Abs(t - y) < TOL Then
recsoln "+" & Format(y)


ElseIf dco.Exists(y) Then
dco(y) = dco(y) + 1


ElseIf y < t - TOL Then
dco.Add Key:=y, Item:=1


c = CDec(c + 1)
Application.StatusBar = "[1] " & Format(c)


End If


End If
Next y


n = dco.Count


ReDim v(1 To n, 1 To 3)


For k = 1 To n
v(k, 1) = dco.Keys(k - 1)
v(k, 2) = dco.Items(k - 1)
Next k


qsortd v, 1, n


For k = n To 1 Step -1
v(k, 3) = v(k, 1) * v(k, 2) + v(IIf(k = n, n, k + 1), 3)
If v(k, 3) t Then dcn.Add Key:="+" & _
Format(v(k, 1)), Item:=v(k, 1)
Next k


On Error GoTo CleanUp
Application.EnableEvents = False
Application.Calculation = xlCalculationManual


For k = 2 To n
dco.RemoveAll
swapo dco, dcn


For Each y In dco.Keys
p = False


For j = 1 To n
If v(j, 3) < t - dco(y) - TOL Then Exit For
x = v(j, 1)
s = "+" & Format(x)
If Right(y, Len(s)) = s Then p = True
If p Then
re.Pattern = "\" & s & "(?=(\+|$))"
If re.Execute(y).Count < v(j, 2) Then
u = dco(y) + x
If Abs(t - u) < TOL Then
recsoln y & s
ElseIf u < t - TOL Then
dcn.Add Key:=y & s, Item:=u
c = CDec(c + 1)
Application.StatusBar = "[" & Format(k) & "] " & _
Format(c)
End If
End If
End If
Next j
Next y


If dcn.Count = 0 Then Exit For
Next k


If (recsoln() = 0) Then _
MsgBox Prompt:="all combinations exhausted", _
Title:="No Solution"


CleanUp:
Application.EnableEvents = True
Application.Calculation = xlCalculationAutomatic
Application.StatusBar = False


End Sub


Private Function recsoln(Optional s As String)
Const OUTPUTWSN As String = "findsums solutions" 'modify to taste


Static r As Range
Dim ws As Worksheet


If s = "" And r Is Nothing Then
On Error Resume Next
Set ws = ActiveWorkbook.Worksheets(OUTPUTWSN)
If ws Is Nothing Then
Err.Clear
Application.ScreenUpdating = False
Set ws = ActiveSheet
Set r = Worksheets.Add.Range("A1")
r.Parent.Name = OUTPUTWSN
ws.Activate
Application.ScreenUpdating = False
Else
ws.Cells.Clear
Set r = ws.Range("A1")
End If
recsoln = 0
ElseIf s = "" Then
recsoln = r.Row - 1
Set r = Nothing
Else
r.Value = s
Set r = r.Offset(1, 0)
recsoln = r.Row - 1
End If
End Function


Private Sub qsortd(v As Variant, lft As Long, rgt As Long)
'ad hoc quicksort subroutine
'translated from Aho, Weinberger & Kernighan,
'"The Awk Programming Language", page 161


Dim j As Long, pvt As Long


If (lft = rgt) Then Exit Sub
swap2 v, lft, lft + Int((rgt - lft + 1) * Rnd)
pvt = lft
For j = lft + 1 To rgt
If v(j, 1) v(lft, 1) Then
pvt = pvt + 1
swap2 v, pvt, j
End If
Next j


swap2 v, lft, pvt


qsortd v, lft, pvt - 1
qsortd v, pvt + 1, rgt
End Sub


Private Sub swap2(v As Variant, i As Long, j As Long)
'modified version of the swap procedure from
'translated from Aho, Weinberger & Kernighan,
'"The Awk Programming Language", page 161


Dim t As Variant, k As Long


For k = LBound(v, 2) To UBound(v, 2)
t = v(i, k)
v(i, k) = v(j, k)
v(j, k) = t
Next k
End Sub


Private Sub swapo(a As Object, b As Object)
Dim t As Object


Set t = a
Set a = b
Set b = t
End Sub
'---- end VBA code ----




"Joshua Jacoby" wrote:

Hmm, well here's the situation. I'm trying to reconcile an account that has
over 300 entries in it for the month of december. So, over 300 debits, but
only say 100 credits. And I'm trying to each credit with the corresponding
bunch of debits. It takes forever to try to do it visually by highlighting
groups of debit entries to match their sum to a credit entry. You understand
what I mean?

"mrice" wrote:


Interesting question

You could do this by using the DEC2BIN function to generate all of the
binary numbers up to two to the power of the count of the numbers that
you have. The individual places could then be used as switches for
whether each number is included in the sum or not. This would allow you
to evaluate all possible combinations and therefore see which matches
your target.


--
mrice

Research Scientist with many years of spreadsheet development experience
------------------------------------------------------------------------
mrice's Profile: http://www.excelforum.com/member.php...o&userid=10931
View this thread: http://www.excelforum.com/showthread...hreadid=540388

I have Excel 2000

"Joshua Jacoby" wrote:

Thank you Peo. Uggghh, I don't think my version has solver. it's not listed
under tools... Well, I guess I can't do it.

"Peo Sjoblom" wrote:

Here it is, this example was done on a small data set but you should be able
to use this technique, instead of 8 in this example you would put the first
credit than use the debits in let's say A2:A308, B2:B308 would have 1s and
so on

"put the data set in let's say A2:A8, in B2:B8 put a set of ones {1,1,1 etc}
in the adjacent cells
in C2 put 8, in D2 put


=SUMPRODUCT(A2:A7,B2:B7)


select D2 and do toolssolver, set target cell $D$2 (should come up
automatically if selected)


Equal to a Value of 8, by changing cells $B$2:$B$7, click add under Subject
to the constraints of:
in Cell reference put


$B$2:$B$7


from dropdown select Bin, click OK and click Solve, Keep solver solution
and look at the table


2 1
4 0
5 0
6 1
9 0
13 0


there you can see that 4 ones have been replaced by zeros and the adjacent
cells to the 2 ones total 8 "


adapt to fit"


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com


"Joshua Jacoby" wrote in message
...
Hmm, I just tried that link and I was denied access to it by my work pc.

"Peo Sjoblom" wrote:

You can use solver,

there was a similar question a few days ago, here's a link

http://tinyurl.com/pfswm


note that the solver that comes with excel is limited in how large data
set
you can use


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com



"Joshua Jacoby" wrote in message
...
I have a long list of monetary amounts listed on an excel spreadsheet.
I
am
trying to find combinations of those amounts that add up to certain
larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or
function
I can use on a large scale for this type of thing?

It is included with excel, but it is an add-in that needs to be installed
either when excel is installed the first time or later, you might have to
ask your IT department for it, they should be able to help.


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com


"Joshua Jacoby" wrote in message
...
Thank you Peo. Uggghh, I don't think my version has solver. it's not
listed
under tools... Well, I guess I can't do it.

"Peo Sjoblom" wrote:

Here it is, this example was done on a small data set but you should be
able
to use this technique, instead of 8 in this example you would put the
first
credit than use the debits in let's say A2:A308, B2:B308 would have 1s
and
so on

"put the data set in let's say A2:A8, in B2:B8 put a set of ones {1,1,1
etc}
in the adjacent cells
in C2 put 8, in D2 put


=SUMPRODUCT(A2:A7,B2:B7)


select D2 and do toolssolver, set target cell $D$2 (should come up
automatically if selected)


Equal to a Value of 8, by changing cells $B$2:$B$7, click add under
Subject
to the constraints of:
in Cell reference put


$B$2:$B$7


from dropdown select Bin, click OK and click Solve, Keep solver solution
and look at the table


2 1
4 0
5 0
6 1
9 0
13 0


there you can see that 4 ones have been replaced by zeros and the
adjacent
cells to the 2 ones total 8 "


adapt to fit"


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com


"Joshua Jacoby" wrote in message
...
Hmm, I just tried that link and I was denied access to it by my work
pc.

"Peo Sjoblom" wrote:

You can use solver,

there was a similar question a few days ago, here's a link

http://tinyurl.com/pfswm


note that the solver that comes with excel is limited in how large
data
set
you can use


--

Regards,

Peo Sjoblom

http://nwexcelsolutions.com



"Joshua Jacoby" wrote in
message
...
I have a long list of monetary amounts listed on an excel
spreadsheet.
I
am
trying to find combinations of those amounts that add up to certain
larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or
function
I can use on a large scale for this type of thing?

Hi,
FYI...
I have seen code that will do what you want. The problem is that with an
unknown number of possibilities that could combine to give you an answer I
believe 300 is way past what excel can handle.

sorry...

good luck

peter

"Joshua Jacoby" wrote:

I have a long list of monetary amounts listed on an excel spreadsheet. I am
trying to find combinations of those amounts that add up to certain larger
sums. For example on a smaller scale:
10
15
21
41
53
How can I find the cells that add up to 108? Is there a formula or function
I can use on a large scale for this type of thing?

Since you are trying to match debits and credits, can you group them by date
and, after getting you IT folks to install Solver for you, run the smaller
groups in Solver?

Seems there should be some other "qualifier" that can limit the debits to
match to a given credit.

Explore Excel's database functions in the Excel Help - especially the query
tables.

"Joshua Jacoby" wrote:

Hmm, well here's the situation. I'm trying to reconcile an account that has
over 300 entries in it for the month of december. So, over 300 debits, but
only say 100 credits. And I'm trying to each credit with the corresponding
bunch of debits. It takes forever to try to do it visually by highlighting
groups of debit entries to match their sum to a credit entry. You understand
what I mean?

"mrice" wrote:


Interesting question

You could do this by using the DEC2BIN function to generate all of the
binary numbers up to two to the power of the count of the numbers that
you have. The individual places could then be used as switches for
whether each number is included in the sum or not. This would allow you
to evaluate all possible combinations and therefore see which matches
your target.


--
mrice

Research Scientist with many years of spreadsheet development experience
------------------------------------------------------------------------
mrice's Profile: http://www.excelforum.com/member.php...o&userid=10931
View this thread: http://www.excelforum.com/showthread...hreadid=540388