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?
Please help me plz
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.
- create a list to hold all solutions
- Test for each number in the set (starting with the passed numberSetIndex and move down):
- if number > total then skip to the next number
- append the number to the partial solution
- if number = total then add this partial solution to the list and move on to the next number
- if number < total then
- call this function again (with total -= number and a copy of the partial solution, and with the current index of the number)
- append all returned solutions
- 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 AllSumsForTotalFromSet.Add partialSolution 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 destCollection.Add e 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)
- Order the list descending
- Use a tree/node structure
- 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
- If the value that it is at is equal to the remaining total, add that value as a child and mark as a solution
- if the value that it is at is greater than the remaining total, mark the branch as not solvable
- 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