How to find all combinations of numbers that equal given sum in Excel
by Alexander Frolov, updated on
3 ways to find all combinations from a set of numbers that sum to a specific total.
Finding combinations of values that add up to a given sum is a common problem in data analysis. For example, you may want to know all possible combinations of items that can be purchased with a given budget, or all possible ways to allocate resources to meet certain requirements. In this article, we will explore how to use Excel Solver and VBA to accomplish the task. We will also discuss some potential pitfalls and limitations of each approach that may arise when handling large datasets or complex constraints.
Find a combination of numbers equal to a given sum with Excel Solver
Regrettably, none of inbuilt Excel functions can help you identify the numbers that add up to a given total. Luckily, Excel provides a special add-in for solving linear programming problems. The Solver add-in is included with all versions of Excel but is not enabled by default. If you are not familiar with this tool, here's a great article on how to add and use Solver in Excel.
With the Solver add-in activated in your Excel, proceed with the following steps:
- Create the model.
For this, enter your set of numbers in one column (A3:A12 in our case) and add a blank column to the right of your numbers for the results (B3:B12). In a separate cell (B13), enter a SUMPRODUCT formula similar to this:
=SUMPRODUCT(A3:A12, B3:B12)
- Run the Solver add-in.
On the Data tab, in the Analysis group, click the Solver button.
- Define the problem for Solver.
In the Solver Parameters dialog box, configure the objective and variable cells:
- In the Set Objective box, enter the address of the formula cell (B13).
- In the To section, select Value Of and type the desired sum value (50 in this example).
- In the By Changing Variable Cells box, select the range to be populated with the results (B3:B12).
- Add the constraints.
To specify the constraints, i.e. the restrictions or conditions that must be met, click the Add button. In the Add Constraint dialog window, select the resulting range (B3:B12) and pick bin from the drop-down list. The Constraint will be automatically set to binary. When done, click OK.
- Solve the problem.
When taken back to the Solver Parameter dialog window, review your settings and click the Solve button.
A few seconds (or minutes) later, the Solver Results dialog box will appear. If successful, select the Keep Solver Solution option, and click OK to exit the dialog.
As a result, you will have 1 inserted next to the numbers that add up to the specified sum. Not a user-friendly solution, but it's the best that out of the box Excel can do.
For visualization purposes, I've highlighted the cells that give the desired sum in light green:
Limitation: Excel Solver can find, at most, just one combination of numbers that equals a specific sum.
Find all combinations that equal a given sum with custom function
To get all possible combinations from a given set of numbers that add up to a certain value, you can use the custom function below. If you are new to UDFs, you'll find a lot of useful information in this guide: How to create custom user defined functions in Excel.
Option Explicit
Public Function FindSumCombinations(rngNumbers As Range, lTargetSum As Long)
Dim arNumbers() As Long, part() As Long
Dim arRes() As String
Dim indI As Long
Dim cellCurr As Range
ReDim arRes(0)
If rngNumbers.Count > 1 Then
ReDim arNumbers(rngNumbers.Count - 1)
indI = 0
For Each cellCurr In rngNumbers
arNumbers(indI) = CLng(cellCurr.Value)
indI = indI + 1
Next cellCurr
Call SumUpRecursiveCombinations(arNumbers, lTargetSum, part(), arRes())
End If
ReDim Preserve arRes(0 To UBound(arRes) - 1)
FindSumCombinations = arRes
End Function
Private Sub SumUpRecursiveCombinations(Numbers() As Long, target As Long, part() As Long, ByRef arRes() As String)
Dim s As Long, i As Long, j As Long, num As Long, indRes As Long
Dim remaining() As Long, partRec() As Long
s = SumArray(part)
If s = target Then
indRes = UBound(arRes)
ReDim Preserve arRes(0 To indRes + 1)
arRes(indRes) = ArrayToString(part)
End If
If s > target Then Exit Sub
If (Not Not Numbers) <> 0 Then
For i = 0 To UBound(Numbers)
Erase remaining()
num = Numbers(i)
For j = i + 1 To UBound(Numbers)
AddToArray remaining, Numbers(j)
Next j
Erase partRec()
CopyArray partRec, part
AddToArray partRec, num
SumUpRecursiveCombinations remaining, target, partRec, arRes
Next i
End If
End Sub
Private Function ArrayToString(x() As Long) As String
Dim n As Long, result As String
result = x(n)
For n = LBound(x) + 1 To UBound(x)
result = result & "," & x(n)
Next n
ArrayToString = result
End Function
Private Function SumArray(x() As Long) As Long
Dim n As Long
SumArray = 0
If (Not Not x) <> 0 Then
For n = LBound(x) To UBound(x)
SumArray = SumArray + x(n)
Next n
End If
End Function
Private Sub AddToArray(arr() As Long, x As Long)
If (Not Not arr) <> 0 Then
ReDim Preserve arr(0 To UBound(arr) + 1)
Else
ReDim Preserve arr(0 To 0)
End If
arr(UBound(arr)) = x
End Sub
Private Sub CopyArray(destination() As Long, source() As Long)
Dim n As Long
If (Not Not source) <> 0 Then
For n = 0 To UBound(source)
AddToArray destination, source(n)
Next n
End If
End Sub
How this function works
The main function, FindSumCombinations, calls a few subsidiary functions that implement smaller sub-tasks. The function named SumUpRecursiveCombinations executes the core algorithm that finds all possible sums in the specified range and filters those that reach the target. The ArrayToString function controls the form of output strings. Three more functions (SumArray, AddToArray, and CopyArray) are responsible for processing intermediate arrays: each time we create a temporary array, add one element from the source array to it, and check if the target sum is reached. The core algorithm is taken from this Stackoverflow thread, thank you guys for sharing!
Syntax
From the user's perspective, the syntax of our custom function is as simple as this:
FindSumCombinations(range, sum)
Where:
- Range is the range of numbers to test.
- Sum is the target sum.
Note! The custom function only works in Dynamic Array Excel 365 and 2021.
How to use the FindSumCombinations function:
- Insert the above code into a Code module of your workbook and save it as a macro-enabled workbook (.xlsm). The step-by-step instructions are here.
- In any blank cell, enter a FindSumCombinations formula and press the Enter key. Make sure there are enough empty cells to the right to output all combinations, otherwise the formula will return a #SPILL error.
For example, to find all possible combinations of numbers in the range A6:A15 that equal the sum in A3, the formula is:
=FindSumCombinations(A6:A15, A3)
As with any other dynamic array function, you enter the formula is just one cell (C6 in the image below) and it populates the results into as many cells as necessary. By default, the comma-separated strings are output in a row:
To return the results in a column, wrap the custom function into TRANSPOSE like this:
=TRANSPOSE(FindSumCombinations(A6:A15, A3))
To output the strings in the form of an array enclosed in curly braces, modify the ArrayToString function as follows:
Private Function ArrayToString(x() As Long) As String
Dim n As Long, result As String
result = "{" & x(n)
For n = LBound(x) + 1 To UBound(x)
result = result & "," & x(n)
Next n
result = result & "}"
ArrayToString = result
End Function
The results will look similar to this:
Limitation: This custom function works only in Dynamic Array Excel 365 and Excel 2021.
Get all combinations that equal a given sum with VBA macro
The custom function described above returns the combinations of numbers as strings. If you'd rather have each number in a separate cell, this macro will be helpful. The code is written by another Excel expert Alexander Trifuntov who has been actively helping users to solve various Excel problems on this blog.
Start by adding the following code to your workbook. For the detailed steps, please see How to insert VBA code in Excel.
Public RefArray1 As String
Public DS As Variant
Public TargetSum As Integer
Public TargetCol As Integer
Public TargetRow As Integer
Sub Combination()
UserForm1.Show
End Sub
Function GrayCode(Items As Variant) As String
Dim CodeVector() As Integer
Dim i, kk, rr, col1, row1, n1, e As Integer
Dim lower As Integer, upper As Integer
Dim SubList As String
Dim NewSub As String
Dim done As Boolean
Dim OddStep As Boolean
Dim SSS
Dim TargetArray() As String
kk = TargetCol
rr = TargetRow
col1 = TargetCol + 3
row1 = TargetRow
OddStep = True
lower = LBound(Items)
upper = UBound(Items)
Cells(rr - 1, kk) = "Result"
Cells(rr - 1, kk + 1) = "Sum"
Cells(rr, kk + 1) = TargetSum
Cells(rr - 1, kk).Font.Bold = True
Cells(rr - 1, kk + 1).Font.Bold = True
ReDim CodeVector(lower To upper) 'it starts all 0
Do Until done
NewSub = ""
For i = lower To upper
If CodeVector(i) = 1 Then
If NewSub = "" Then
NewSub = "," & Items(i)
SSS = SSS + Items(i)
Else
NewSub = NewSub & "," & Items(i)
SSS = SSS + Items(i)
End If
End If
Next i
If NewSub = "" Then NewSub = "{}" 'empty set
SubList = SubList & vbCrLf & NewSub
If SSS = TargetSum Then
Cells(rr, kk) = Mid(NewSub, 2)
TargetArray() = Split(Mid(NewSub, 2), ",")
n1 = UBound(TargetArray)
For e = 0 To n1
Cells(row1, col1) = TargetArray(e)
row1 = row1 + 1
Next e
col1 = col1 + 1
row1 = TargetRow
rr = rr + 1
End If
SSS = 0
'now update code vector
If OddStep Then
'just flip first bit
CodeVector(lower) = 1 - CodeVector(lower)
Else
'first locate first 1
i = lower
Do While CodeVector(i) <> 1
i = i + 1
Loop
'done if i = upper:
If i = upper Then
done = True
Else
'if not done then flip the *next* bit:
i = i + 1
CodeVector(i) = 1 - CodeVector(i)
End If
End If
OddStep = Not OddStep 'toggles between even and odd steps
Loop
GrayCode = SubList
End Function
Next, create a UserForm with the following design and properties:
Tip. Instead of re-creating the form from scratch, you can download our sample workbook at the end of this post and copy the Code module and UserForm1 from there (see how to copy a macro to another workbook). To make the macro accessible in all your workbooks, copy it to the Personal Macro Workbook.
With the code and form in place, press Alt + F8 and run the FindAllCombinations macro:
On the form that pops up, define the following:
- The range with the source numbers (A4:A13)
- The target sum (50)
- The upper-left cell of the destination range (C4).
When specifying the upper-left cell of the output range, make sure there is at least one blank row above (for headers) and enough blank cells down and to the right. If there are insufficient blank cells, your existing data will be overwritten.
Clicking OK will produce the result like shown in the screenshot below:
- In C4:C6, you have the combinations of numbers as comma-separated values.
- Columns F, G and H hold the same combinations of numbers, with each number residing in a separate cell.
- In D4, you have the target sum.
This form of output makes it easier to check the result - just enter the SUM formula in cell F13, drag it to the right across two more cells and you will see that each combination of numbers adds up to the specified value (50).
Limitation: For a large set of numbers, the macro may take some time to generate all possible combinations.
Advantages: Works in all versions of Excel 2010 - 365; provides two forms of output - strings of comma separated values and numbers.
In conclusion, finding all combinations of values that equal a certain value is a powerful tool for solving a wide range of data analysis problems. Hopefully, this article has provided you with a useful starting point for exploring this topic further and handling similar problems in your own work. Thank you for reading!
Practice workbook
Find combinations that equals a given sum - examples (.xlsm file)
You may also be interested in
Table of contents
