Get list of numbers form Array Whose sum is X

Question

I have a number let say 27 and a list of NumbersList. How do I get some selected numbers from NumbersList whose some is 27. And also using the most greater numbers from NumbersList It can be done by going threw all the possibilities but deep down I know there is a simple solution and I am overthinking it.

#available numbers
NumbersList = [1,5,9,4,6,8,12,12,1,3,6,8,7,8,2]

def GetNumbers(number):
    global NumbersList
    tmpList = []

    #Some magical code

    return tmpList


#now result have
result = GetNumbers(27)
# result is  [12, 12, 3]
# 12+12+3 using most possible greater numbers from "NumbersList"

Leo Arad · Accepted Answer · 2020-06-23T13:09:16.140

2

You can try

NumbersList = [1,5,9,4,6,8,12,12,1,3,6,8,7,8,2]

def GetNumbers(number):        
    result = []
    for i in sorted(NumbersList, reverse=True):
        if sum(result) + i <= number:
            result.append(i)
    return result

OR if the NumbersList is large then you can reduce iteration by

def GetNumbers(number):
    result = []
    for i in sorted(NumbersList, reverse=True):
        sum_list = sum(result)
        if sum_list + i == number:
            result.append(i)
            return result
        elif sum_list + i < number:
            result.append(i)
    return result

print(GetNumbers(27))

Output

[12, 12, 3]

edited Jun 23 '20 at 13:09

answered Jun 23 '20 at 13:01

Leo Arad

4,452
2
6
17

How do I give priority to the numbers that are in ending of the list instead of greater numbers? – Maulik Lathiya Jun 24 '20 at 13:14
Removing the reverse=True from the sort method – Leo Arad Jun 24 '20 at 13:29

score 1 · Answer 2 · answered Jun 23 '20 at 13:02

This is one way to do it

NumbersList = [1,5,9,4,6,8,12,12,1,3,6,8,7,8,2]

def GetNumbers(NumbersList, number):
    tmpList = []
    summ = 0
    srtd = sorted(NumbersList)
    for i in range(len(srtd)-1, 0, -1):
        if summ + srtd[i] > number:
            break
        summ += srtd[i]
        tmpList.append(srtd[i])
    for i in range(len(NumbersList)):
        if NumbersList[i] == number - summ:
            tmpList.append(NumbersList[i])
    if sum(tmpList) == number:
        return tmpList
    else:
        return None

result = GetNumbers(NumbersList, 27)
print(result)

Certainly not the best, but does the work for this one.

First, you sort the list, find all the biggest numbers which does not exceeds the limit. Then you find the missing number. If there is, return the array. If there is not, we return None.

This code will not work for all cases, but a good one to start with.

Easyest way to do it, is to sort the list, loop it through backwards, then

Is there room for the next number?

If there is, you can add it to the list.
If there is not, skip.

At the end you should check the sum of yout tmpList. There is a possibility that its sum is != your intended number.

Get list of numbers form Array Whose sum is X

2 Answers2