Sum of all the subsets whose sum is a Perfect Number from a given array

Approach

The idea is straightforward; we generate all the possible subsets from the given array using a recursive function. We simply pass the sum of the subsets to another function named isPerfectSubsetSum(), where we check whether the passed number is a Perfect Number or not.

In the isPerfectSubsetSum()  function, we calculate all the divisors and then check whether the sum of the divisors equals the number.

Finding all the divisors

All of the divisors are present in pairs if we look closely. For instance, if n = 50, the divisors are (1,50), (2,25), and (5,10). One of the divisors in every pair is present before or till √n.

So, we can run for loop using this condition (i * i <= n) and find one of the divisors of every pair. Simultaneously we can find the other divisor of the pair by dividing the number with the calculated divisor.

We can significantly speed up our program if we take advantage of finding the divisors using the above efficient approach. If the Number(sum of the subset passed) is a Perfect Number, we just print it.

Let’s understand the above approach with an example:

a[] = {6, 3, 28, 3}
All the possible subsets are: {6}, {3}, {28}, {3}, {6,3}, {6,28}, {6,3}, {3,28}, {28,3}, {3,3}, {6,3,28}, {6,3,3}, {6,28,3}, {3,3,28}, {6,3,28,3}
Perfect subset sums are: 
{6} = 6
{28} = 28   // divisors sum = 1+2+4+7+14 = 28, perfect number
{3,3} = 6

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int isPerfectSubsetSum(int n)
{
  int sum = 1;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)
    {
      if (i * i != n)
        sum += i + (n / i);
      else
        sum += i;
    }
  }

  if (sum == n) {
    return 1;
  }
  else
    return 0;
}

void subSum(int arr[], int l, int r, int sum = 0)
{

  if (l > r) {


    if (isPerfectSubsetSum(sum)) {
      cout << sum << " ";
    }
    return;
  }


  subSum(arr, l + 1, r, sum + arr[l]);

  subSum(arr, l + 1, r, sum);
}

int main()
{
  int arr[] = { 6, 3, 28, 3 };
  int N = sizeof(arr) / sizeof(arr[0]);
  subSum(arr, 0, N - 1);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

6 6 28

Complexity Analysis

Time complexity: The time complexity is O(total_sum * 2^n) as the number of subsets is 2^n, and for each subset-sum, we are checking, it is a perfect number or not where total_sum is the sum of all elements in the given array.

Space complexity: O(1), as we are using constant extra space.

Frequently Asked Questions

What is a Perfect Number?

If the sum of proper divisors of a number, that is, the sum of its positive divisors excluding the number itself, is equal to the number itself, it is said to be a perfect number.

What is the Space Complexity of the function to check whether the given number is a Perfect Number?

The Space Complexity of the function to check whether the given number is a Perfect Number is √n  as we are using a loop of size √n. 

Why do we have to run a for loop until √n times to find the divisors?

We have only to run the for loop till √n times to find the divisors because one of the divisors in every pair is present before or up to √n. We can run for loop using this condition (i * i <= num) and find one of the divisors of every pair. Simultaneously we can find the other divisor of the pair by dividing n with the calculated divisor.

Conclusion

This article discussed the perfect number and approach to finding the Sum of all the subsets whose sum is a Perfect Number from a given array with examples and C++ code.

Recommended Problems: 

• Number Of Subsets
• Subset Sum Equal To K
• Minimum Subset Sum Difference
   

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is absolutely free! 

Thank you for reading!