Question

Дано N попарно различных целых чисел.

Рассмотрим все непустые подмножества данного набора чисел (их ровно 2N − 1).

Для каждого подмножества вычислим сумму его элементов.

Отсортируем все полученные суммы по невозрастанию.

Ваша задача — найти K-ю в полученном порядке сумму подмножества.

ПОМОГИТЕ СРОЧНО!!!

Answer 1

Программа:

Python:

def kth_subset_sum(numbers, k):

   import itertools

   subset_sums = []

   for i in range(1, len(numbers) + 1):

       subsets = itertools.combinations(numbers, i)

       for subset in subsets:

           subset_sums.append(sum(subset))

   subset_sums = sorted(set(subset_sums))

   

   return subset_sums[k-1]

Пример использования (дописать в конце файла):

numbers = [1, 2, 3, 4]

k = 5

print(kth_subset_sum(numbers, k)) # output: 5

Объяснение:

Эта реализация использует функцию itertools.combinations из модуля itertools для генерации всех подмножеств по номерам входящего в функцию списка. Подмножества суммируются, суммы результатов сортируются и сохраняются в списке subset_sums. И в конце программы возвращается сумма k - 1.