# Perfect Sum Problem

Given an array of integers and a sum, the task is to count all subsets of a given array with the sum equal to the given sum.

**Problem Description:**

The problem asks you to find the number of subsets that are elements from the given array such that their sum is equal to given sum in the problem, subset size can be one if a single element is equal to a given sum or greater than one depending upon the input array.

For example: For [5,6,7,8,9] and sum = 5, the subset is {5} as a single element is equal to a given sum and for sum==12 the subset{5,7} makes it possible therefore subset size is greater than one is also possible.

**Input**: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains n space-separated integers forming the array. The last line contains the sum.

**Output**: Count all the subsets of the given array with the sum equal to the given sum.

**Example:**

Input:
T = 1
N = 5
[5,6,7,8,9]
Sum = 12
Output:
1
Explanation:
{7+5} = 12 therefore this is the required subset.
INPUT:
T = 1
N = 5
[1,2,3,4,0]
Sum = 5
Output:
2, {1+4} = 5 and {2+3} = 5 therefore they are the required subset.

1) Recursive ApproachWe will use the recursive function solve to evaluate the count of subsets that are equal to the given sum.

We consider the following base cases:

if sum==0:There is an empty subset that satisfies the given case, so wereturn1.if n==0 and sum!=0:There is no subset that is possible to construct soreturn 0.if(arr[n-1]>sum): Since we are checking from last to first order (n to 0) index and we are using 0 based indexing system, we can’t take this element because the value of this element is greater than the required sum so we call recursive function for rest of the element.i.e,solve(arr,n-1,sum)+solve(arr,n-1,sum-arr[n-1])Time Complexity for the above approach is exponential.

Program to illustrate the working of recursive approachOutput:Dynamic Programming Approach:TOP-DOWN APPROACH:

Here we take

dp[n][sum]as our dynamic state. Initially, we will fill the entire dp state as -1, if the dp state is calculated then its value changes so if the recursion call is made again then we first check it in the dp table whether it is calculated or not. If calculated already then simply return it, otherwise calculate it.Follow steps are used in top-down dp:

dp[][]state that will help in storing the value for some statedp[i][j]such that i is the index for an element which will be used and j is the required sum value.dp[][]state is filled with -1 for memoization as discussed above.dp[i][j]state without recalculating it.dp[i][j]state we would simply calculate according to recursion.O(n*n).Time complexity for above approach is

O(n*n)Space Complexity for above approach is

O(n*n)Program to illustrate the working of Top-down dynamic programming approachOutput:BOTTOM UP APPROACH:

In this case we will fill the

dp[n][sum]state in bottom up manner. We will fill the base cases as:dp[n][sum]=0dp[n][sum]=1dp[i][j]=dp[i-1][j]+d[i-1][j-arr[i-1]]here we check for both cases.Follow steps would be used in bottom-up dp:

dp[i][j]stateiis the number of elements that are we using for our current sumj.dp[i][j]wherejis thesum==0, then every empty subset is possible so we makedp[i][0]=1dp[i][j]wherei==0, we can not make any subset therefore it will be 0.dp[i][j]we have two cases either we include a current element or we can not include. For this case, we need our sum j need to be greater than the element present at index (i-1) 0 based index. Otherwise, we can not include it so we simply assign till previous index-based value.O(n*n)Time Complexity for above approach is

O(n*n)Space Complexity for above approach is

O(n*n)Program to illustrate the working of bottom-up dynamic programming approach

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: