Сумма всех подмножеств, сумма которых является совершенным числом из данного массива

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

Примеры:

Input: arr[] = {5, 4, 6}
Output: 6
Explanation:
All possible subsets from the array arr[] are:
{5} → Sum = 5
{4} → Sum = 4.
{6} → Sum = 6.
{5, 4} → Sum = 9.
{5, 6} → Sum = 11.
{4, 6} → Sum = 10.
{5, 4, 6} → Sum = 15.
Out of all subset sums, only 6 sums are found to be2` a perfect number.

Input: arr[] = {28, 6, 23, 3, 3}
Output: 28 6 6

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

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

Временная сложность: O(M * 2 ^N ), где M — сумма элементов массива arr[]
Вспомогательное пространство: O(1)

Итеративный подход: Поскольку существует 2 ^N возможных подмножеств из массива размера N , идея состоит в том, чтобы повторить цикл от 0 до 2N – 1 и для каждого числа выбрать все элементы массива, которые соответствуют 1 s в двоичном представлении массива. текущее число, а затем проверьте, является ли сумма выбранных элементов совершенным числом или нет. Выполните следующие шаги, чтобы решить проблему:

• Выполните итерацию в диапазоне [0, 2 ^N – 1] , используя переменную i , и выполните следующие шаги:
  • Инициализируйте переменную, скажем, S с 0 , чтобы сохранить сумму текущего подмножества.
  • Перейдите массив arr[] с помощью переменной j и выполните следующие шаги:
    • Если j ^-я позиция установлено в двоичном представлении i , добавьте значение arr[j] к S .
  • Проверьте, является ли S совершенным числом или нет, если окажется, что оно верно , выведите значение S как результат.

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

Временная сложность: O((N + M) * 2 ^N ), где M — сумма элементов массива , arr[]
Вспомогательное пространство: O(1)