which combinations of numbers in a set add up to a given total

I've been looking for solution of one mathematical problem

I have fix set of numbers [65536, 131072, 262144, 524288, 104576, 2097152]

I will have some total of above numbers only

but my problem is how I can get a combination of numbers in given total?

My solution is very similar to Davids.

Assumption: The set of numbers is ordered ascending.

Call the function and start with the highest number, pass an empty partial solution and try to calculate all possible sums of the set of numbers that return total. The sums are returned as a Collection.

The function:

1. create a list to hold all solutions
2. Test for each number in the set (starting with the passed numberSetIndex and move down):
2. append the number to the partial solution
3. if number = total then add this partial solution to the list and move on to the next number
4. if number < total then
1. call this function again (with total -= number and a copy of the partial solution, and with the current index of the number)
2. append all returned solutions
3. return all solutions

Watch out: I did not understand if you wanted to use each number of the set only once for the sum, so the code below will also calculate sums that contain more than one instance of a number in the given set. If you want each number to appear only once, locate the line Set result = AllSumsForTotalFromSet(total - number, numberSet, index, CopyAndReDimPlus1(partialSolution)) in the function Function AllSumsForTotalFromSet and replace index with index-1 in the recursive call.

```Sub Test_AllSumsForTotalFromSet()
Dim numberSet, total As Long, result As Collection

numberSet = Array(65536, 131072, 262144, 524288, 104576, 2097152)
total = 366720

Set result = GetAllSumsForTotalFromSet(total, numberSet)

Debug.Print "Possible sums: " & result.count

PrintResult result
End Sub

Function GetAllSumsForTotalFromSet(total As Long, ByRef numberSet As Variant) As Collection
Set GetAllSumsForTotalFromSet = New Collection
Dim partialSolution(1 To 1) As Long

Set GetAllSumsForTotalFromSet = AllSumsForTotalFromSet(total, numberSet, UBound(numberSet), partialSolution)
End Function

Function AllSumsForTotalFromSet(total As Long, ByRef numberSet As Variant, numberSetIndex As Long, ByRef partialSolution() As Long) As Collection
Dim index As Long, number As Long, result As Collection

Set AllSumsForTotalFromSet = New Collection

'break if numberSetIndex is too small
If numberSetIndex < LBound(numberSet) Then Exit Function

For index = numberSetIndex To LBound(numberSet) Step -1
number = numberSet(index)

If number <= total Then
'append the number to the partial solution
partialSolution(UBound(partialSolution)) = number

If number = total Then

Else
Set result = AllSumsForTotalFromSet(total - number, numberSet, index, CopyAndReDimPlus1(partialSolution))
AppendCollection AllSumsForTotalFromSet, result
End If
End If
Next index
End Function

'copy the passed array and increase the copy's size by 1
Function CopyAndReDimPlus1(ByVal sourceArray As Variant) As Long()
Dim i As Long, destArray() As Long
ReDim destArray(LBound(sourceArray) To UBound(sourceArray) + 1)

For i = LBound(sourceArray) To UBound(sourceArray)
destArray(i) = sourceArray(i)
Next i

CopyAndReDimPlus1 = destArray
End Function

'append sourceCollection to destCollection
Sub AppendCollection(ByRef destCollection As Collection, ByRef sourceCollection As Collection)
Dim e
For Each e In sourceCollection
Next e
End Sub

Sub PrintResult(ByRef result As Collection)
Dim r, a

For Each r In result
For Each a In r
Debug.Print a;
Next
Debug.Print
Next
End Sub
```

Interesting thought experiment... here is my solution (pre-warning - no code, only algorithm)

1. Order the list descending
2. Use a tree/node structure
3. Write a recursive loop that traverses the list. If the value that it is at is less than the remaining value, add that value as a child
4. If the value that it is at is equal to the remaining total, add that value as a child and mark as a solution
5. if the value that it is at is greater than the remaining total, mark the branch as not solvable
6. IF the end of the list is reached, mark that branch as not solvable

You should end up with a tree representing the valid solutions. Example:

```set = [50,40,30,20,15,10,5]
total required = 60
Solution tree
root
50 -> 10
40 -> 20
-> 15 -> 5
30 -> 20 -> 10
-> 15 -> 10 -> 5
```