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.

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):
    1. if number > total then skip to the next number
    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
                AllSumsForTotalFromSet.Add partialSolution

                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;
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
    50 -> 10
    40 -> 20
       -> 15 -> 5
    30 -> 20 -> 10
       -> 15 -> 10 -> 5

Need Your Help

In .net, how do I choose between a Decimal and a Double

.net floating-point

We were discussing this the other day at work and I wish there was a Stackoverflow question I would point people at so here goes.)

How to show desired number of elements in list according to if else condition?

jquery list

I want to show only desired number of elements in list when I click on button (say 3 number of itesm will be shown according to input condition) How would I accomplish it?