Which Numbers Sum to Target

Download Recursion1.zip

The problem: You have a list of numbers, some of which sum up to another number. If you have 10 numbers, there are 2^10 or 1,024 possible combinations. A pretty daunting task.

Recursion to the rescue. This file allows you to enter a list of numbers and a target, and it will tell you which numbers sum to the target.

excel range showing a subset of numbers that sum to a target

Naishad Rajani wrote the code and Jimmy Day prettied up the UI. I only have the distinction of distributing the file. I did spend quite a bit of time stepping through this macro about five years ago. I had never used recursion at the time, and it was difficult to get my head around.

A word of warning. Twenty items in the list seems to be about the upper limit from a time perspective. Any more than that and it takes too long to process.

64 thoughts on “Which Numbers Sum to Target

  1. Harlan Grove’s procedure kicks the recursive code’s butt.

    For what it’s worth, I’ve used the same recursive version for the last 7 years or so – but I think it was originally posted on the web by Michel Claes.

    Copy the code below into a code module, and set the references as instructed in the comments.

    Then run findsums and highlight the ranges with your values when prompted.

    MS Excel MVP

    Option Explicit
    ‘Begin VBA Code

    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
    Exit Sub
    End If

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

    If VarType(y) = vbBoolean Then
    Exit Sub
    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) 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
    swapo dco, dcn

    For Each y In dco.Keys
    p = False

    For j = 1 To n
    If v(j, 3) = 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 —

  2. I tried the workbook: Impressive!

    Would like to try your code too Dick but is it possible you cannot set the reference to
    “Microsoft VBScript Regular Expressions 1.0 or higher”
    in XL97?

    Brgds Sige

  3. Bernie graciously sent me a copy of the code from Michael a while ago. I modified it a tad and added it as a button on a custom menu. Here is my code. It basically is the same as Bernies except that it finds all of the solutions and lets the user see the possibles one after the other. Bernies actually show the last of possibly many solutions. Select a range and run the code. It will prompt you for a number. Then just let it rip. If it is taking too long hit escape. If the range is more than 25 elements it warns you that this could take a while…

    ‘ Original solution created by
    ‘ Michel Claes

    Private Const intWarningElements As Integer = 25
    Private dblTargetValue As Double
    Private intElements As Integer
    Private intCurrentSolutionFlags() As Integer
    Private intBestSolutionFlags() As Integer
    Private dblElementValues() As Double
    Private dblBestSolution As Double
    Private rngRangeToSearch As Range
    Private blnFound As Boolean

    Public Sub FindSolution()
    Dim intCounter As Integer
    Dim wks As Worksheet

    Set wks = ActiveSheet
    Set rngRangeToSearch = Intersect(Selection, wks.UsedRange)
    If rngRangeToSearch Is Nothing Then Set rngRangeToSearch = ActiveCell
    dblBestSolution = 0
    dblTargetValue = GetTargetValue
    intElements = rngRangeToSearch.Count
    ReDim dblElementValues(intElements)
    ReDim intBestSolutionFlags(intElements)
    ReDim intCurrentSolutionFlags(intElements)

    If intElements > intWarningElements Then
    If MsgBox(“This may take a VERY long time to execute. Did you wish ” & _
    “to proceed?”, vbYesNo + vbCritical, “Proceed???”) = vbYes Then
    Call ProcessSelection
    End If
    Call ProcessSelection
    End If

    If blnFound = False Then
    Call StoreSolution
    MsgBox “The search is completed.”, vbInformation, “Complete”
    End If
    Set wks = Nothing
    End Sub

    Private Sub ProcessSelection()
    Dim intCounter As Integer

    Application.StatusBar = “Processing. Please Wait.”
    For intCounter = 1 To intElements
    On Error Resume Next
    dblElementValues(intCounter) = rngRangeToSearch.Item(intCounter)
    On Error GoTo 0
    Next intCounter
    Evaluate 0, 1
    Application.StatusBar = False

    End Sub

    Private Sub StoreSolution()
    Dim intCounter As Integer
    Dim rngFound As Range

    For intCounter = 1 To intElements
    If intBestSolutionFlags(intCounter) = 1 Then
    If rngFound Is Nothing Then
    Set rngFound = rngRangeToSearch.Item(intCounter)
    Set rngFound = Union(rngRangeToSearch.Item(intCounter), rngFound)
    End If
    End If
    Next intCounter
    If rngFound Is Nothing Then Set rngFound = ActiveCell
    If Round(Application.Sum(rngFound), 4) Round(dblTargetValue, 4) Then _
    MsgBox “An exact match was not found. The closest match is:” & _
    vbCrLf & vbCrLf & vbTab & _
    Format(Application.Sum(rngFound), “#,##0.00?) & _
    vbCrLf & vbCrLf & “A difference of:” & vbCrLf & vbCrLf & vbTab & _
    Format(Application.Sum(rngFound) – dblTargetValue, “#,##0.00?)
    Set rngFound = Nothing
    End Sub

    Private Sub CopySolutionFlags()
    Dim intCounter As Integer

    For intCounter = 1 To intElements
    intBestSolutionFlags(intCounter) = intCurrentSolutionFlags(intCounter)
    Next intCounter
    End Sub

    Private Sub Evaluate(ByVal total As Double, ByVal pos As Integer)
    On Error GoTo HandleCancel
    Application.EnableCancelKey = xlErrorHandler

    If pos 0 Then blnInputOk = True
    End If

    Do While blnInputOk = False
    MsgBox “The value entered must be a number not equal to 0. ” & _
    “Please try again.”, vbInformation, “Input Error”
    strInput = InputBox(“Please enter the target value.”, “Target Value”)
    If strInput = Empty Then End
    If Not IsNumeric(strInput) Then
    If CDbl(strInput) 0 Then blnInputOk = True
    End If
    GetTargetValue = CDbl(strInput)
    End Function

  4. Jim,

    Did you have a problem pasting your code? The last sub has an End Function statement rather than an End Sub, so there appears to be a chunk missing.


  5. Dick/Jim T,

    Can either of you send me the workbook also, I am having the same problem. The recursion1.zip file will not download for me from the link for some reason.

  6. Can either of you send me the workbook also, I am having the same problem. The recursion1.zip file will not download for me from the link for some reason.

  7. Bernie,

    It looks like there is an error in the line

    If Abs(t – y) t Then dcn.Add Key:=”+” & _

    Is there supposed to be something between “(t-y)” and the “t”

  8. Bernie,

    There is also an issue with

    Call recsoln

    There is nothing called “recsoln” for it to call??

  9. Fred: It’s no doubt a greater than or less than sign which WordPress incorrectly interprets as html. Posting code in the comments of this blog stinks and I take full responsibility for it. The ‘recsoln’ I can’t account for.

  10. Hello,

    I was wondering if the code can be modified slightly to gain all possible combinations that are less than or equal to a target number.


  11. Sorry, I also would like to have a constraint that the combination of numbers always has to contain the same amount of cell references (ie. combinations have to have 11 different cell references (numbers))

    Eg. 250 numbers, exactly 11 numbers must be chosen, the sum of these numbers must be less than or equal to 1000.


  12. Hi Dick,

    Can we see the Recursion2 available for download. Just love that code.


  13. kanwaljit: I looked for it last night, but couldn’t find it. I’m sure it’s there somewhere. I’ll look again tonight and hopefully get it posted this weekend.

  14. I don’t know how well behaved Bernie’s post or various revisions of Harlan’s code or any of the variants of the recursive solutions are. My gut instinct would be to ask if any of them follow the developments from the world of Operations Research, specifically, the Simplex method. Luckily, Solver uses just that method when told that the problem is a “linear problem.” For a template, see
    Find a set of amounts that match a target value

  15. Hi Dick,

    Thanks a million to both of you. I was Delighted to see the reply. Thanks Dick, would love to wait for the file !
    Thanks a lot Tushar, I really got mad searching for something to do that. Just saw yours comment. Feels jubilated, just on seeing the link. A link to something on yours site. Must be perfect, I believe. Let me try that.

    Best Regards

  16. Hi,

    It seems the Recursion file given on this site suits my requirements in a better way. While I am trying my best to make the things work for me, it would help me a lot, If I have a chance to try the Said 2nd Recursion.zip. Dick, Do upload the file, if you can find it. Hopefully.

    Thanks and Regards

  17. Very unfortunate for me………. What to do now ? Does anyone of the other participants have a copy of it ? If Bernie or Jim or anyone else has saved a copy of it, please request them on my behalf to provide a copy of it.

    Thanks and Regards

  18. I keep this in my custom add-in with a toolbar button to the TargetFinder macro. I basically took the code from the recursion model workbook posted in a prior comment out of the template worksheet and adapted it to work on whatever items you have selected at the moment. I find it very useful when trying to figure out what accounts were rolled up into a total account in financial statements. I wish I could understand Tushar’s code enough to set it up in a similar way. As it stands right now, I can barely run this against 22 numbers on a 2GHz Core2Duo rig before it’s too slow to bear.

    Option Explicit
    Dim dblTarget As Double
    Dim intElements As Integer
    Dim intStat() As Integer
    Dim intStatb() As Integer
    Dim dblElements() As Double
    Dim dblBest As Double
    Dim rngInputCells() As Range
    Sub StoreIt()
    Dim intCount As Integer
    Dim dblClosest As Double
    Dim rngResult As Range

        For intCount = 1 To intElements
            If intStatb(intCount) = 1 Then
                dblClosest = dblClosest + rngInputCells(intCount).Value
                If rngResult Is Nothing Then
                    Set rngResult = rngInputCells(intCount)
                    Set rngResult = Union(rngResult, rngInputCells(intCount))
                End If
            End If
        Next intCount
        If Not rngResult Is Nothing Then rngResult.Select
        If dblClosest = 0 Then
            MsgBox “An answer could not be found”, vbInformation, “Unsolvable”
            If MsgBox(“You searched for “ & Format(dblTarget, “#,###.00”) & “.” & vbCrLf & “The closest answer is “ & Format(dblClosest, “#,###.00”) & “.” & vbCrLf & vbCrLf & “Press Yes to highlight these in red.” & vbCrLf & vbCrLf, vbInformation + vbYesNo, “Result”) = vbYes Then
                rngResult.Interior.ColorIndex = 3
            End If
        End If

    End Sub
    Sub CopyIt()
    Dim intCount As Integer
        For intCount = 1 To intElements
            intStatb(intCount) = intStat(intCount)
        Next intCount

    End Sub
    Sub Evaluate(ByVal total As Double, ByVal pos As Integer)
        If pos  0 Then ‘skip zeros
                   If Not dblElements(1) = 0 Then ‘don’t redim first time
                       ReDim Preserve dblElements(1 To UBound(dblElements) + 1)
                        ReDim Preserve rngInputCells(1 To UBound(rngInputCells) + 1)
                    End If
                    dblElements(UBound(dblElements)) = CDbl(rngCell.Value)
                    Set rngInputCells(UBound(rngInputCells)) = rngCell
                End If
            End If
        If UBound(dblElements) > 20 Then
            If MsgBox(“You selected “ & UBound(dblElements) & ” items.  Anything over 20 may take a very long time to calculate.  Are you sure you want to continue?”, vbExclamation + vbYesNo, “Are you sure?”) = vbNo Then Exit Sub
        End If
        ReDim intStat(1 To UBound(dblElements))
        ReDim intStatb(1 To UBound(dblElements))
        dblBest = 0
        dblTarget = Application.InputBox(“What is the Target amount?”, “Target”, Type:=1)
        intElements = UBound(dblElements)
        Evaluate 0, 1

    End Sub

  19. Hi,

    When searching the internet for my ‘problem’, I found your emailchain that looks exactly what I was looking for. Never realized it would take so much time to come to sollutions for subsets larger than 25 items, I have sets of 100 items and larger… But I couldn’t find the Jim T sollution, I would love to have this code that will show all possible sollutions and not just one possible sollution. Dick Kusleika says it is posted on the intranet, but I cann’t find it back. Can you please send it to me?

    By the way I love this excel forum! Realy good.



  20. Could one of you guys contact me (matt.j.steele@gmail.com) about the recursion formulas shown in this blog. I am prepared to pay for a excel spreadsheet solution that involves multiple targets from a list of data, using each value in the data list only once. I would also like to receive a copy of the spreadsheet that Dick Kusleika said he would post on internet back in 2005. Thanks.-

  21. question about a code

    Dear Mr .
    At this address i found a very nice code.
    I put it on Excel and with macro it is working good.
    But i want to find the solution at the next 2 problems.If you can , please teach me how to made the code.
    For exemple before the code is running i want to make to appear a mesage like this


    Or another condition:
    I want to write some arrays on the excel sheet:
    array1 from AC5:DD5 first array
    array2 from AC6:DD6 second.
    array3 from AC7:DD7
    array4 from AC8:DD8
    array n from ACn:DDn
    Then i want a code that read one after another this arrays and take only m numbers
    from an array.
    So the combinations that apearrs must contain only m numbers from this arrays

    array1 from AC5:DD5 first array
    array2 from AC6:DD6 second.
    array3 from AC7:DD7
    array4 from AC8:DD8
    array n from ACn:DDn

    If you can help me THANK YOU.
    If you canot then i must surf the Web.
    Thank you for your time and consideration.

  22. The posted example can also be solved quickly without code…
    In cell C1, ctrl+shift+enter:


    (or use row(b1:b262144) in xl2007). Now fill down from C3:


    For other solutions you can use SMALL(,k) in place of MIN().

  23. 1000 points to you.
    I was presented the problem,
    tried to solve it myself,
    realized it would be difficult to code, (for me, at least)
    found the name of the problem,
    searched google,
    and found you had already created the solver for me!

    I’m thrilled, Thanks.


  24. Just downloaded Recursion1.zip and it works perfectly! It’s a little slow with 30 to 40 combinations but all told it’s a life saver. I don’t know about the rest of you but I will be using this when I reconcile my credit card deposits in QuickBooks Pro. For the last 2 years I’ve cussed QB for not having this built in. THANKS!

  25. This is great & I have used it on some smaller ranges, however on bigger ranges the number of possible combinations is extremly large & can be very slow.

    For example I may have 200 numbers, but the figure I am looking for is probably made up of a combination of just 5 or fewer of these. How can I get the code just to look at these smaller combinations?

    This way I can do a quicker check & if nothing is found, re-run for 10 number combinations, 15 etc, until I find the result.

  26. I think I have a faster solution in cases where you want to limit the number of items in the total, or the total number of possible solutions. It uses a couple of computer chess tricks (like pre-storing a large number of combinations). For example, given a target figure, I can find
    * 8 items out of 60 items, in 20 seconds
    * 5 items out of 200 items, in under a minute

    Obviously, it gets much slower for more items, or where there are many possible solutions, but it should be pretty effective for business solutions.

    It can definitely be made more efficient, and it hasn’t been independently checked, because I did it just for fun, so I haven’t fine tuned it, but I’m happy to share it.

    Write to me at dermot dot balson at gmail dot com if you’d like a copy

  27. HELP PLEASE :)

    I get an error when my list of numbers exceed 30. The list i’m trying to work from has 700 numbers in the list. Has anyone been sucessful using this with a large range?

    The error i get is below:
    elems(i) = Cells(i + 2, 2)

    any help would be greatly appreciated!


  28. FYI to future readers

    In response to Camilla’s post the number records that can be processed can be increased by changing the length of the variables.


    instead of:

    Global stat(30) AS Integer
    Global statb(30) AS Double
    Global elems(30) As Double


    Global stat(60) AS Integer
    Global statb(60) AS Double
    Global elems(60) As Double

    this will allow you to use up to 60 values in the equation.

    NOTE: using this many values will SIGNIFICANTLY increase the time taken to calculate!

  29. Thanks a lot; I just needed this macro for a otherwise seemingly unsolvable problem.

    Kind regards,


    I get an error when my list of numbers exceed 30. The list i’m trying to work from has 700 numbers in the list. Has anyone been sucessful using this with a large range?

    The error i get is below:
    elems(i) = Cells(i + 2, 2)

    any help would be greatly appreciated!


  31. Dear Chandu,

    Whether there is any excel commands also. I do not want to use macro and want to get the target with formula. Please help.

  32. Ajay – In Excel 2007+, you can try with CTRL+SHIFT+ENTER in C3:C20 of Dick’s example above :


    This takes only around a second to recalculate if the values are changed and the size of the range can be adjusted up to 20 values. You can also change the {1} in the formula to {1,2} and array-enter in multiple columns to get the two closest combinations of values.

    Note: You first need to save the posted file in XLSM format and open in a new session to view the larger grid.

  33. benzadeus,



  34. Dear Sir,

    There are a set of debit values and a set ot credit values in a column. I want a vba code by whcich the debit value plus a single / multiple credit value is zero that needs to be marked .

    finally i will come to know out of the avaibale debits which cannot be used the with avilable credits either single or multiple values.

    If multiple matching sets are available let it take the 1st or the 2nd one its not an issue.

    Column A Ref

    -1000 A
    -5000 B
    -8000 C

    800 A
    100 A
    100 A
    2000 B
    3000 B

    Thanks in Advance

  35. Dear benzadeus,

    I have fond code but hot to oprate in excel pls. let me know,

    Sub MG11Apr43
    Dim Rng As Range, Dn As Range
    Dim Deb As Double
    Dim Cred As Double
    Dim col As Integer
    Dim Q As Variant
    Dim Ray As Variant
    Dim Del As Integer
    Set Rng = Range(Range(“B2”), Range(“B” & rows.Count).End(xlUp))
    With CreateObject(“scripting.dictionary”)
    .CompareMode = vbTextCompare
    For Each Dn In Rng
    If Dn.Offset(, -1) 0 Then
    Cred = Dn.Offset(, -1)
    End If
    If Not .Exists(Dn.value) Then
    .Add Dn.value, Array(Dn.Address, Deb, Cred, “”)
    Q = .Item(Dn.value)
    If Dn.Offset(, -1) > 0 Then
    Q(2) = Q(2) + Dn.Offset(, -1)
    Q(1) = Dn.Offset(, -1)
    End If
    If Q(3) = “” Then
    Q(3) = Q(3) & Q(0) & “,” & Dn.Address
    Q(3) = Q(3) & “,” & Dn.Address
    End If
    If Q(1) + Q(2) = 0 Then
    col = col + 1
    Ray = Split(Q(3), “,”)
    For Del = 0 To UBound(Ray)
    Range(Ray(Del)).Offset(, 1) = col
    Next Del
    End If
    .Item(Dn.value) = Q
    End If
    Deb = 0: Cred = 0
    End With
    End Sub


  36. I’m trying to rewrite this code in php, Can you please advice me the Data flow. so I can convert this. I tried lots of combination, it gets me a Memory exceeded error.

  37. If you’re running out of memory, it’s most likely because you never get out of the recursion. The program flow is recursive, so explaining it here won’t help. The ‘eval’ procedure calls itself. You need to make sure that eval has a path where it doesn’t call itself anymore (if pos>nbr_elem, eval stops calling itself).

  38. Dear all,

    I have find minimum value into sheet1 a1,sheet2 a1, sheet3 a1, sheet4 a1. result is ref. a2 (in sheet 1 to 4)


  39. Hi,

    Please help me to find some solution for the below.

    I have 200 row’s which consist Positive values & Negative values. I would like to find which are all making a target value. example: My target value is -10 and the result should be which are the item’s making up this total.


  40. If you had Excel 64-bit and a Cray supercomputer, it would probably still take a month to do that with 200 rows. On my machine, sum to target takes the following times:

    Number of Items Time in Seconds
    10 1
    20 4
    25 126
    30 9200

    That last one is bout 2.5 hours. Those are max times.

    It think you need to find a different program or, better yet, a different approach than Excel.

  41. Pingback: concrete sum
  42. Srini, we have an algorithm for this kind of problems. It is VERY FAST. It will be released as SumMatch Pro in a few months time.
    For now I am happy to try it on your numbers. I need you to post the numbers and the target value.

  43. Is there an update on this? It seems like the most referenced site, but the zip file at the top is not active.

  44. Hi – wondering if there is code to only output the results that sum four of the numbers in the range (or other such specified number), that sum to the specified total? Instead of getting all possible combinations.


Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.