# Finding all possible combinations of numbers to reach a given sum

## Recommended Posts

Any ideas about writing fast code finding all possible combinations of numbers to reach a given sum (target) in a matrix???

example: Target 12

[7,8,5,3,2,1,4,6]

[2,6,5,5,2,1,1,9]

[1,4,5,1,2,1,4,3]

[3,8,5,3,6,4,2,6]

[6,8,5,9,2,1,4,6]

All possible combinations: 7+5, 7+3+2, 7+1+4, 8+3+1, and so on....

Thanks !!!

##### Share on other sites

Looks like a difficult math problem that one.

I'm curious, is there is a practical purpose to this?

Monkey's are, like, natures humans.

##### Share on other sites

Welcome to the AutoIt forums.

An interesting little problem. This code seems to work:

```#include <Array.au3>

\$iRequiredSum = 12

Global \$aArray = [7, 8, 5, 3, 2, 1, 4, 6]

; Increase the number of factors on each pass
For \$iSet = 1 To UBound(\$aArray)
; Determine the possible combinations
\$aCombinations = _ArrayCombinations(\$aArray, \$iSet, "+")
; For each combination
For \$j = 1 To \$aCombinations[0]
; Break into factors
\$aFactors = StringSplit(\$aCombinations[\$j], "+")
; Sum factors
\$iSum = 0
For \$k = 1 To \$aFactors[0]
\$iSum += \$aFactors[\$k]
Next
; If sum is required value
If \$iSum = \$iRequiredSum Then
; Write caombination
ConsoleWrite(\$aCombinations[\$j] & " = " & \$iRequiredSum & @CRLF)
EndIf
Next
Next```

The result:

```7+5 = 12
8+4 = 12
7+3+2 = 12
7+1+4 = 12
8+3+1 = 12
5+3+4 = 12
5+1+6 = 12
2+4+6 = 12
5+2+1+4 = 12
3+2+1+6 = 12```

M23

Edited by Melba23
Typo

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites
26 minutes ago, JohnOne said:

Looks like a difficult math problem that one.

I'm curious, is there is a practical purpose to this?

Yep... Avoid using excel

##### Share on other sites
2 hours ago, Melba23 said:

That's pretty cool Melba23 !! ;-D

What about to consider only one solution (the first one possible) for a specific number of factors and skip to the next one:

i.e.

7+5, (the first possible for 2 factors)

7+3+2, (the first possible for 3 factors)

5+2+1+4 (the first possible for 4 factors)

Thanks!!!!!!

Edited by Melba23
Removed quote

##### Share on other sites

Just add ExitLoop after the ConsoleWrite line.

##### Share on other sites

When you reply, please use the "Reply to this topic" button at the top of the thread or the "Reply to this topic" editor at the bottom rather than the "Quote" button - I know what I wrote and it just pads the thread unnecessarily.

As to just displaying the first result for each number of factors this looks as if it does what you want:

```#include <Array.au3>

\$iRequiredSum = 12

Global \$aArray = [7, 8, 5, 3, 2, 1, 4, 6]

; Increase the number of factors on each pass
For \$iSet = 1 To UBound(\$aArray)
; Determine the possible combinations
\$aCombinations = _ArrayCombinations(\$aArray, \$iSet, "+")
; For each combination
For \$j = 1 To \$aCombinations[0]
; Break into factors
\$aFactors = StringSplit(\$aCombinations[\$j], "+")
; Sum factors
\$iSum = 0
For \$k = 1 To \$aFactors[0]
\$iSum += \$aFactors[\$k]
; Are we over the required sum?
If \$iSum > \$iRequiredSum Then
; No point in adding further factors <<<<<<<
ExitLoop
EndIf
Next
; If sum is required value
If \$iSum = \$iRequiredSum Then
; Write first combination found for this number of factors <<<<<<<<<
ConsoleWrite("For " & \$iSet & " factors" & @CRLF & \$aCombinations[\$j] & " = " & \$iRequiredSum & @CRLF)
; Move immediately to increase the number of factors <<<<<<<<<
ExitLoop
EndIf
Next
Next```

Result:

```For 2 factors
7+5 = 12
For 3 factors
7+3+2 = 12
For 4 factors
5+2+1+4 = 12```

M23

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites

Sorry...

Thank you for your precious help!

##### Share on other sites
On 15/2/2016 at 2:31 PM, ferradavi said:

Sorry...

Thank you for your precious help!

Hi Melba23,

I'm in a trouble

When I use the script in a 9x9 grid it runs so slow.

Expecially if the number of factors is 4.  If higher I get "Array maximum size exceeded"..

Do you have any suggestion to find only the first solution useful to get the target, skipping all possible combinations?

Thanks

grid.au3

##### Share on other sites

The error is obvious - line #345 is completely wrong!

If you want a sensible answer, how about posting the code you are using - see here how to do it

M23

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites

Thank you... That's it!

```#include <Array.au3>

\$iRequiredSum = 27

Global \$aArray = [1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9, _
1,2,3,4,5,6,7,8,9]

; Increase the number of factors on each pass
For \$iSet = 1 To UBound(\$aArray)
; Determine the possible combinations
\$aCombinations = _ArrayCombinations(\$aArray, \$iSet, "+")
; For each combination
For \$j = 1 To \$aCombinations[0]
; Break into factors
\$aFactors = StringSplit(\$aCombinations[\$j], "+")
; Sum factors
\$iSum = 0
For \$k = 1 To \$aFactors[0]
\$iSum += \$aFactors[\$k]
; Are we over the required sum?
If \$iSum > \$iRequiredSum Then
; No point in adding further factors <<<<<<<
ExitLoop
EndIf
Next
; If sum is required value
If \$iSum = \$iRequiredSum Then
; Write first combination found for this number of factors <<<<<<<<<
ConsoleWrite("For " & \$iSet & " factors" & @CRLF & \$aCombinations[\$j] & " = " & \$iRequiredSum & @CRLF)
; Move immediately to increase the number of factors <<<<<<<<<
ExitLoop
EndIf
Next
Next```

Do you have any suggestion to find only the first solution useful to get the target number?

##### Share on other sites

That is not a 9x9 grid - that is a single list of 81 elements. So it is hardly surprising that you run into problems as the possible number of small set-size combinations of those 81 elements is extremely large.

So let us see if we can approach this a different way, but first I need some more information:

• Are those values representative - i.e. are they always integers from 1 to 9?
• Is there any limit to the number of repeat instances for any element - can there be anywhere between 0 or 81 repeats?

M23

Edited by Melba23
Formatting

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites

Ok

Yes they are always integers from 1 to 9, but they are generated in a random way and order.

It's sufficient to obtain one result, the first one possible to get the target number. If the target is between 2 to 18, obviously two factors are good...and also fast

To get an higher target number, such as 27, the number of factors starts from 3, but if there aren't 3 elements in the list the number of factors must be higher: 4, 5, 6 etc.

i.e. to obtain 27, if I start from the first element in the list:

```Global \$aArray = [1,2,2,3,1,1,6,3,4, _
4,2,3,4,5,6,7,8,9, _
7,2,3,4,5,1,7,2,9, _
9,2,3,9,5,5,7,1,9, _
3,2,1,2,3,6,6,6,4, _
3,2,3,4,5,6,7,8,9, _
2,2,3,8,1,4,7,1,9, _
1,7,3,9,5,6,7,1,2, _
7,2,3,7,5,1,7,8,5]```

I have minimum 3 factors = 9+9+9 (infact I cannot obtain 27 with only 2 factors).

In the next example the solution cannot be reached from the sum of 3 factors, because there are only 2 elements marked 9 (the first and the last)... so to obtain 27 it's necessary to consider the sum of 4 factors and if we cannot obtain the target in this way it's necessary to consider the sum of 5 factors and so on. The target can be an integer from 11 to 100.

```Global \$aArray = [9,2,2,3,1,1,6,3,4, _
4,2,3,4,5,6,7,8,7, _
7,2,3,4,5,1,7,2,2, _
2,2,3,1,5,5,7,1,4, _
3,2,1,2,3,6,6,6,4, _
3,2,3,4,5,6,7,8,3, _
2,2,3,8,1,4,7,1,2, _
1,7,3,5,5,6,7,1,2, _
7,2,3,7,5,1,7,8,9]```

Which is the fastest way to do this?

##### Share on other sites

You are introducing more and more constraints on this problem - before I devote any more time to trying to solve this, please explain why you need to do this.

M23

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites

here is a long way to determine factors, certainly not optimal

```;arrayFactors
#include<array.au3>

\$target = 27

Global \$aArray = [9,2,2,3,1,1,6,3,4, _
4,2,3,4,5,6,7,8,7, _
7,2,3,4,5,1,7,2,2, _
2,2,3,1,5,5,7,1,4, _
3,2,1,2,3,6,6,6,4, _
3,2,3,4,5,6,7,8,3, _
2,2,3,8,1,4,7,1,2, _
1,7,3,5,5,6,7,1,2, _
7,2,3,7,5,1,7,8,9]

\$aWork = \$aArray

\$max1 = _ArrayMaxIndex(\$aWork , 1)
_ArrayDelete(\$aWork , \$max1)

\$max2 = _ArrayMaxIndex(\$aWork , 1)
_ArrayDelete(\$aWork , \$max2)

If \$aArray[\$max1] + \$aArray[\$max2] >= \$target Then
msgbox(0, '' , "2 factor min")
Else
\$max3 = _ArrayMaxIndex(\$aWork , 1)
_ArrayDelete(\$aWork , \$max3)
EndIf

If \$aArray[\$max1] + \$aArray[\$max2] + \$aArray[\$max3] >= \$target Then
msgbox(0, '' , "3 factor min")
Else
\$max4 = _ArrayMaxIndex(\$aWork , 1)
_ArrayDelete(\$aWork , \$max4)
EndIf

If \$aArray[\$max1] + \$aArray[\$max2] + \$aArray[\$max3] + \$aArray[\$max4] >= \$target Then
msgbox(0, '' , "4 factor min")
Else
\$max5 = _ArrayMaxIndex(\$aWork , 1)
_ArrayDelete(\$aWork , \$max5)
EndIf```

```,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)```

##### Share on other sites

With a little lateral thinking I have a really good, fast solution to the problem, but I am still awaiting an explanation as to why you need to do this.

M23

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites

shrunk mine some

```;arrayFactors
#include<array.au3>

\$target = 27

Global \$aArray = [9,2,2,3,1,1,6,3,4, _
4,2,3,4,5,6,7,8,7, _
7,2,3,4,5,1,7,2,2, _
2,2,3,1,5,5,7,1,4, _
3,2,1,2,3,6,6,6,4, _
3,2,3,4,5,6,7,8,3, _
2,2,3,8,1,4,7,1,2, _
1,7,3,5,5,6,7,1,2, _
7,2,3,7,5,1,7,8,9]

\$aWork = \$aArray
_ArraySort(\$aWork , 1)

for \$i = 2 to ubound(\$aWork)
\$total = execute(_ArrayToString(\$aWork , "+" , -1 , \$i))
If \$total >= \$target then
msgbox(0, '' , "minimum of " & \$i & " factors")
Exit
EndIf
next```

```,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)```

##### Share on other sites

This is a difficult math problem we discuss in our classes to develop a smart, fast and efficient algorithm.

##### Share on other sites

Fine. My "lateral thinking" led me to the idea that to minimize the number of factors required you should use as many of the higher value ones as possible and then use the smaller ones to "fill in". So that is what happens in this script:

```#include <Array.au3>
#include <MsgBoxConstants.au3>

Local \$iMaxPossible = 0

; Create random 81 elements and calculate eh max possible value
Global \$aFactors[81]
For \$i = 0 To 80
\$aFactors[\$i] = Random(1, 9, 1)
\$iMaxPossible += \$aFactors[\$i]
Next

; Determine required number
\$iRequired = Random(1, \$iMaxPossible, 1)
ConsoleWrite("Required: " & \$iRequired & @CRLF)

;_ArrayDisplay(\$aFactors, "", Default, 8)

; Count number of each separate element
Global \$aFactorCount[10]
For \$i = 0 To 80
\$aFactorCount[\$aFactors[\$i]] += 1

Next

;_ArrayDisplay(\$aFactorCount, "", Default, 8)

; Declare variables
Local \$iTotal = 0, \$iRemainder = \$iRequired, \$sFactors = ""

; Starting with the highest element
For \$iFactorValue = 9 To 1 Step -1
; How many can be used to reach the required value
\$iFactorReq = Int(\$iRemainder / \$iFactorValue)
; if there are not enough, then only use the available number
If \$iFactorReq > \$aFactorCount[\$iFactorValue] Then
\$iFactorReq = \$aFactorCount[\$iFactorValue]
EndIf
; Adjust values for next pass and create result string
For \$j = 1 To \$iFactorReq
\$iTotal += \$iFactorValue
\$iRemainder -= \$iFactorValue
\$sFactors &= \$iFactorValue & "+"
Next
; if required total reached then stop
If \$iTotal = \$iRequired Then
ExitLoop
EndIf

Next

If \$iTotal = \$iRequired Then
ConsoleWrite(StringTrimRight(\$sFactors, 1) & "=" & \$iRequired & @CRLF)
Else
ConsoleWrite("Unable to factor " & \$iRequired & @CRLF)
EndIf

_ArrayDisplay(\$aFactorCount, "", Default, 8)```

M23

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

##### Share on other sites

This is the classical problem in additive number theory (also called additive combinatorics theory).

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

## Create an account

Register a new account