474,007 Members | 21,872 Online

Find sum in a list

25 New Member
I am using VB in excel and I have a list of numbers in column A and I am trying to find which numbers match up to make a sum of another number. The list of numbers is quite lengthy, and there may be more then one combination.

Ex.

List = 1 2 3 4 5 6
Sum = 10
output = 1,2,3,4 and 1,3,6 and 1,4,5 and 2,3,5 and 4,6

Any ideas?
Mar 10 '08 #1
18 7282
1,295 Recognized Expert Top Contributor
I am using VB in excel and I have a list of numbers in column A and I am trying to find which numbers match up to make a sum of another number. The list of numbers is quite lengthy, and there may be more then one combination.

Ex.

List = 1 2 3 4 5 6
Sum = 10
output = 1,2,3,4 and 1,3,6 and 1,4,5 and 2,3,5 and 4,6

Any ideas?
Its not as easy as you think. A not very hard way (but not very efficient) will be creating all the posibles combinations: 2^n, and check the ones that satisfy the sum.
i'd make a matrix of 2^n x 2, where for each combination, we'll have the combination and its sum, then check sum by sum if it matches with your number.
e.g.
list: 1, 2, 3
sum = 3

the matrix will be of 2^3 = 8 x 2 (actually 7x2, because we'll not consider the empty one)
the matrix will look like his:
Expand|Select|Wrap|Line Numbers
1. combination     sum
2.   1               1
3.   2               2
4.   3               3
5.   1,2             3
6.   1,3             4
7.   2,3             5
8.   1,2,3           6
and the entrances it'll return will be 3 and 1,2.

With some recursivity, it can be done.

HTH
Mar 11 '08 #2
Killer42
8,435 Recognized Expert Expert
It's a very interesting problem, and one which I feel should be directed toward any mathematicians present. It's really not a VB-specific question, but one of deriving an algorithm to handle the situation. Given the algorithm we can easily (probably) translate to VB.

Kadghar, I think that if anything, you've underestimated the number of possible combinations.

EDIT: I've dropped a post into the Software Development forum asking anyone interested to have a look here.
Mar 11 '08 #3
1,295 Recognized Expert Top Contributor
...
Kadghar, I think that if anything, you've underestimated the number of possible combinations.
...
Sounds like a challenge to me!!
^.^

Well, since its late at night, i wont make the best algorithm, but this one will work if the list has less than 170 numbers (because a double wont allow any factorial over 170, and im using combinations)

This is made for Excel's VBA, it'll read the list from column A (there shouldnt be blank spaces) and reads the sum from cell B1.

It wont work if any value of the list is repeated, and it wont show the obvious solution (i.e.it wont show the solutions of only one number, only combinations of 2 or more members of the list)

Expand|Select|Wrap|Line Numbers
1. Sub FindCombinations()
2. Dim a, Var1
3. Dim b()
4. Dim Result() As String, Result2() As String
5. Dim Dou1 As Double
6. Dim i As Integer
7. a = Range(Cells(1, 1), Cells(1, 1).End(-4121))
8. Dou1 = Cells(1, 2)
9. ReDim b(1 To UBound(a) - 1)
10. b(1) = TwoNums(a, a)
11. For i = 2 To UBound(b)
12.     b(i) = nNums(b, a, i)
13. Next
14. ReDim Result(1 To 1)
15. For Each Var1 In b
16.     For i = 1 To UBound(Var1)
17.         If Var1(i, 2) = Dou1 Then
18.             ReDim Preserve Result(1 To UBound(Result) + 1)
19.             Result(UBound(Result)) = Var1(i, 1)
20.         End If
21.     Next
22. Next
23. ReDim Result2(1 To UBound(Result) - 1, 1 To 1)
24. For i = 2 To UBound(Result)
25.     Result2(i - 1, 1) = Result(i)
26. Next
27. Range(Cells(1, 3), Cells(UBound(Result) - 1, 3)) = Result2
28. End Sub
29. Function TwoNums(Arr1, Arr2)
30. Dim i As Long: Dim j As Long: Dim k As Long
31. Dim Arr3() As String
32. 'array with 2 nums
33. ReDim Arr3(1 To Combinations(UBound(Arr1), 2), 1 To 2)
34. For i = 1 To UBound(Arr1)
35.     If Mid\$(Arr1(i, 1), InStrRev(Arr1(i, 1), ",") + 1) <> Arr2(UBound(Arr2), 1) Then
36.     For j = i + 1 To UBound(Arr2)
37.         k = k + 1
38.         Arr3(k, 1) = Arr1(i, 1) & "," & Arr2(j, 1)
39.         Arr3(k, 2) = Val(Arr1(i, 1) + Arr2(j, 1))
40.     Next
41.     End If
42. Next
43. TwoNums = Arr3
44. End Function
45. Function nNums(Arr1, Arr2, n As Integer)
46. Dim i As Long: Dim j As Long: Dim k As Long
47. Dim Boo1 As Boolean
48. Dim Arr3() As String
49. ReDim Arr3(1 To Combinations(UBound(Arr2), n + 1), 1 To 2)
50. For i = 1 To UBound(Arr1(n - 1))
51.     Boo1 = False
52.     For j = 1 To UBound(Arr2)
53.         If Boo1 = True Then
54.             k = k + 1
55.             Arr3(k, 1) = Arr1(n - 1)(i, 1) & "," & Arr2(j, 1)
56.             Arr3(k, 2) = CDbl(Val(Arr1(n - 1)(i, 2)) + Val(Arr2(j, 1)))
57.             End If
58.         If Mid\$(Arr1(n - 1)(i, 1), InStrRev(Arr1(n - 1)(i, 1), ",") + 1) = Arr2(j, 1) Then Boo1 = True
59.     Next
60. Next
61. nNums = Arr3
62. End Function
63.
64. Function Factorial(ByVal i As Integer) As Double
65. Factorial = 1
66. While i > 1
67.     Factorial = Factorial * i
68.     i = i - 1
69. Wend
70. End Function
71. Function Combinations(n As Integer, k As Integer) As Double
72. Combinations = Factorial(n) / (Factorial(k) * Factorial(n - k))
73. End Function
^.^ wasnt that hard (anyway, it can be improved, this one is not efficient)
Mar 11 '08 #4
if1467
25 New Member
Sounds like a challenge to me!!
^.^

Well, since its late at night, i wont make the best algorithm, but this one will work if the list has less than 170 numbers (because a double wont allow any factorial over 170, and im using combinations)

This is made for Excel's VBA, it'll read the list from column A (there shouldnt be blank spaces) and reads the sum from cell B1.

It wont work if any value of the list is repeated, and it wont show the obvious solution (i.e.it wont show the solutions of only one number, only combinations of 2 or more members of the list)

^.^ wasnt that hard (anyway, it can be improved, this one is not efficient)
So I tried this on the actual numbers I have (did i forget to mention that there are 49 in this particuliar set) and my computer returned "Do I look like I cost more than \$1,500?".

So.....any more efficient ideas would be greatly appreciated or a donation to my supercomputer fund.

kadghar - thanks for your effort, it works great on small sets of numbers!!
Mar 11 '08 #5
1,295 Recognized Expert Top Contributor
So I tried this on the actual numbers I have (did i forget to mention that there are 49 in this particuliar set) and my computer returned "Do I look like I cost more than \$1,500?".

So.....any more efficient ideas would be greatly appreciated or a donation to my supercomputer fund.

kadghar - thanks for your effort, it works great on small sets of numbers!!
Are you aware that you have 2^49 - 1 = 562'949'953'421 '311 possible combinations?
And with my awesome deductive power, i'd say you computer didnt cost over \$1,500.
To evaluate an IF/THEN should take it about 1 / 10^7 seconds. So... assuming you already have all the posible combinations and their values. And you only want to check if its value is the same as the SUM. That'll take 56'294'995 seconds.
That is 1 year, 9months, 16 days (aprox).

But, since you dont have all the combinations yet, neither their values, i'd say that in 50, may be 60 years you'll get your result.

The only thing that comes to my mind now is... in order to make this somehow faster, i'll recomend you to sort the list, then take the biggest number, smaller than the SUM, and check number by number, if it wont make your tmpResult exceed the SUM take it, once you find a good combination, start with some other number, and so on... many times.. This way you wont get all the possible combinations, but you can control how many results you want. May be the first 10 are good enough for what you need.
Mar 11 '08 #6
1,295 Recognized Expert Top Contributor
oh, i forgot..
may be another solution will be, for 49 numbers, there are
1176 combinations of 2 numbers
18424 of 3
211876 of 4
1906884 of 5
13983816 of 6

this means that if you only want the possible combinations with 6 or less numbers, we're talking of 16'122'176 combinations. I think this will take only a few minutes, and the result might be helpful

Actually, if you want the combinations of 10 numbers or less, they are 10'825'278'996. Im sure you can get them in 3 or 4 hours.

Note:
To do this just change line 9
ReDim b(1 To n-1)
e.g ReDim b(1 to 9) will do for up to 10 ^.^
Mar 11 '08 #7
if1467
25 New Member
oh, i forgot..
may be another solution will be, for 49 numbers, there are
1176 combinations of 2 numbers
18424 of 3
211876 of 4
1906884 of 5
13983816 of 6

this means that if you only want the possible combinations with 6 or less numbers, we're talking of 16'122'176 combinations. I think this will take only a few minutes, and the result might be helpful

Actually, if you want the combinations of 10 numbers or less, they are 10'825'278'996. Im sure you can get them in 3 or 4 hours.

Note:
To do this just change line 9
ReDim b(1 To n-1)
e.g ReDim b(1 to 9) will do for up to 10 ^.^
What if I wanted to put a limit on the number of outputs. For example, take the first 5 combinations that work, or even better only take the first combination. Do you think that would help, and how would I modify your code to do this?
Mar 11 '08 #8
1,295 Recognized Expert Top Contributor
What if I wanted to put a limit on the number of outputs. For example, take the first 5 combinations that work, or even better only take the first combination. Do you think that would help, and how would I modify your code to do this?
yes, that might help, but you'll have to make a different code.

this code, first get all the combinations and its sum, then checks every sum. It uses some kind of recursivity to create the combinations of each size (it starts with size 2, then 3, and so on)
What you can do for sure, is to make it do all combinations for 2 and 3

redim b(1 to 2)

it wont take more than 5 seconds, and hopefully, you'll get more than some answers.

HTH
Mar 11 '08 #9
1,295 Recognized Expert Top Contributor
i fill the A column with numbers from 1 to 49

then i asked for the 2, 3 and 4 number combinations that sum 98 (well, there will be only of 3 and 4, since 49+48 = 97).

It took less than 10 seconds to show me there are 3'172 posible ways to sum 98 using 3 or 4 numbers from 1 to 49. Thats a nice result.

Oh, please note i made a mistake, i declared some integers, change them to longs, or even better, to doubles (you shouldnt have any problem by doing this).
Mar 11 '08 #10