Algorithm to get closest number set

[SonicWave]

Good day,

Let say we hv a number set {11, 22, 33, 44, 55, 66, 77, 88, 99, 111}. Is there any algorithm that can give me a subset {x1, x2, x3, ...} where the sum of the subset closest and less than to 150 , for example ?

E.g.,

11+22 = 33
11+22+33+44 = 110
11+22+33+44+55 = 165

So the answer using the above example would be {11, 22, 33, 44} as it gives the closest 10 150. Is there any algorithm to get this set ?

Thanks.

SonicWave

[Guitarism]

this is probably way too messy and can be done better BUT

Dim answer As String
    Dim counter As Integer
    Dim sum As Integer
    Dim goal As Integer
    Dim i As Integer
    Dim myArray(10) As Integer
    myArray(0) = 11
    myArray(1) = 22
    myArray(2) = 33
    myArray(3) = 44
    myArray(4) = 55
    myArray(5) = 66
    myArray(6) = 77
    myArray(7) = 88
    myArray(8) = 99
    myArray(9) = 111
    counter = 0
    sum = 0
    goal = 150
    answer = ""
    i = 0
    
    Do While counter < (UBound(myArray()) - 1)
        sum = sum + myArray(counter)
 
        If sum = goal Then
                Do While i <= counter
                    answer = answer & " " & myArray(i)
                    i = i + 1
                Loop
            
            MsgBox ("{" & answer & "}" & " added together = " & sum & " which is closest to and less than " & goal)
            Exit Do
        End If
            
        If sum > goal Then
            sum = sum - myArray(counter)
                Do While i <= counter
                    answer = answer & " " & myArray(i)
                    i = i + 1
                Loop
            MsgBox ("{" & answer & "}" & " added together = " & sum & " which is closest to and less than " & goal)
            Exit Do
        End If
        counter = counter + 1
    Loop

[Logophobic]

Is it necessary that your subset contain only consecutive members of the number set?

If not, then the solution for the example number set and target sum is:
11 + 22 + 111 = 144
33 + 111 = 144

A simple recursive subroutine can easily find all these sums.

[Guitarism]

I think so Logo; the way he gives examples shows that.

Also "subset {x1, x2, x3, ...} " implies consecutive members.

[NotLKH]

But must the first element of the subset be the first element of the set?

In other words, could {66 77} be considered?