Лучший способ получить количество элементов списка, сумма значений которых равна постоянному значению. ⇐ Python

[Anonymous]

У меня есть список, состоящий из числовых значений.
В Python он записывается так:

Код: Выделить всё

[959, 3480, 9346, 8367, 2847, 8330, 6946, 9586, 9722, 2775]

Или в случае MySQL:

Код: Выделить всё

create table testtb(n int);
insert into testtb values(959),(3480),(9346),(8367),(2847),(8330),(6946),(9586),(9722),(2775);

Мне хотелось найти в списке элементы с суммой 43219.
Я считал, что SQL — не лучший выбор, поэтому выбрал программирование и закончил его.
Вот как я сделал это на Python с помощью следующего скрипта:

Код: Выделить всё

import random
ls=[959, 3480, 9346, 8367, 2847, 8330, 6946, 9586, 9722, 2775]
length=len(ls)

flag=True
while flag:
new_ls=random.sample(ls,length) #get a list with the same elements but in different order
print(f'\n\na new list with the following combination begins: {new_ls}')
total=0
index=0
for n in new_ls:
total=total+n
if total>43219:  #there is no need to keep on using the current list
break
elif total==43219:  #found the answer
print(f'\nfound the combination:{new_ls[:index+1]}')
print(f'it has a length of {index+1}')
print(f'the sorted list is:{sorted(new_ls[:index+1])}')
flag=False
break
index+=1

После запуска скрипта я получил ответ после нескольких неудачных комбинаций:

Код: Выделить всё

a new list with the following combination begins: [8330, 9346, 8367, 9722, 959, 9586, 2847, 3480, 6946, 2775]

a new list with the following combination begins: [6946, 2847, 2775, 959, 8367, 8330, 3480, 9346, 9586, 9722]

a new list with the following combination begins: [2775, 3480, 959, 8367, 9586, 9722, 8330, 6946, 9346, 2847]

found the combination:[2775, 3480, 959, 8367, 9586, 9722, 8330]
it has a length of 7
the sorted list is:[959, 2775, 3480, 8330, 8367, 9586, 9722]

Конечно, подобное можно сделать и в MySQL. Временную таблицу можно создать с помощью:

Код: Выделить всё

select n from testtb order by rand();

Затем используйте курсор, чтобы получить значение из каждой строки и добавить их одну за другой. И сравните сумму с постоянным значением.
В любом случае проблема в том, что разрешение слишком сильно зависит от случайности. Есть ли лучший способ добиться этого в Python или MySQL?

Подробнее здесь: https://stackoverflow.com/questions/798 ... constant-v