Сумма всех подмножеств заданного размера (=K)

Опубликовано: 21 Сентября, 2022

Дан массив arr[] , состоящий из N целых чисел и положительного целого числа K , задача состоит в том, чтобы найти сумму всех подмножеств размера K .

Примеры:

Input: arr[] = {1, 2, 4, 5}, K = 2
Output: 36
Explanation:
The subsets of size K(= 2) are = {1, 2}, {1, 4}, {1, 5}, {2, 4}, {2, 5}, {4, 5}. Now, the sum of all subsets sum = 3 + 5 + 6 + 6 + 7 + 9 = 36.

Input: arr[] = {2, 4, 5, 6, 8}, K=3
Output: 150

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные подмножества данного массива и найти сумму элементов этих подмножеств, размер которых равен K . Найдя сумму всех подмножеств размера K , выведите сумму всех сумм, полученных в результате.

Временная сложность: O(K* 2N )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, если учесть тот факт, что количество вхождений каждого элемента arr[i] в ряд суммирования зависит от значений N и K.

Найдем вхождение общего элемента x в ряд суммирования:

  • Встречаемость x в ряду суммирования всех подмножеств size=k = n-1 C k-1

Следовательно, частота каждого элемента arr[] одинакова в уравнении суммирования = n-1 C k-1 . Следовательно, сумма всех подмножеств = (Сумма всех элементов массива) * n-1 C k-1 .

Выполните следующие шаги, чтобы решить данную проблему:

  • Инициализируйте переменную, скажем, freq как 0 и вычислите n-1 C k-1
  • Инициализируйте переменную, скажем, sum как 0 , чтобы сохранить сумму всех элементов массива.
  • После выполнения вышеуказанных шагов выведите значение sum*freq как результирующую сумму.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ