## Introduction

This blog will discuss the approach to the sum of all the subsets whose sum is a "perfect number".

Before jumping into the question, let’s learn about the perfect number. So, without any further ado, let’s get started!

**What is a Perfect Number?**

If the sum of all the proper divisors of a number, excluding the number itself, is equal to the number, it is called a perfect number.

Let us understand it with examples:

**Example - 1:**

```
Input: 6
Output: True
Explanation
The divisors of 6 are 3, 2, and 1. The sum of divisors is 1+3+2 = 6 is the number itself. So it is a Perfect Number.
```

**Example - 2:**

```
Input: 10
Output: False
Explanation
The divisors of 10 are 2, 5, and 1. The sum of divisors is 1+2+5 = 8, which is not the number itself. So it is not a Perfect Number.
```

Recommended topic about, __kth largest element in an array__, and __Euclid GCD Algorithm__

### Problem statement

We are given an array having n elements. Our task is to find the sum of all the subsets whose sum is a Perfect Number in the given array.

### Sample Example

```
Input: a[]={6, 3, 2}
Output: 6
Explanation
The possible subsets of array a[] are:
{6}, {3}, {2}, {6,3}, {6,2}, {3,2}, {6, 3, 2}
Sum of all the subsets:
{6}= 6 // perfect number
{3}= 3 // not a perfect number
{2}= 2 // not a perfect number
{6,3}= 9 // not a perfect number
{6,2}= 8 // not a perfect number
{3,2}= 5 // not a perfect number
{6, 3, 2}= 11 // not a perfect number
Among all the values of the sum of subsets, only 6 is a perfect square.
So the output is 6.
```

## 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
```