Perfect Sum Problem Geeks for Geeks

 class Solution{

public int perfectSum(int arr[],int n, int sum) 

{ 

    int t[][]=new int[n+1][sum+1];

    for(int i=0;i<n+1;i++){

        for(int j=0;j<sum+1;j++){

            if(i==0){

                t[i][j]=0;

            }

            if(j==0){

                t[i][j]=1;

            }

        }

    }

    int count=0;

    for(int i=1;i<n+1;i++){

        for(int j=1;j<sum+1;j++){

            if(arr[i-1]>j){

                t[i][j]=t[i-1][j] % 1000000007;

            }

            else{

                t[i][j]=((t[i-1][j-arr[i-1]]) + (t[i-1][j])) %1000000007;

               

            }

        }

    }

    

    

    return (t[n][sum])%1000000007;

} 

}

Problem Statement: Here we have to count the pairs which have sums equal to a given value.

Approach: Here we will initialize the int array with 0 and 1 for two cases.

1.It is not possible that given array is empty and sum is finite(except 0) so for all i==0 t[i][j]=0

2.It is possible that if a given array is not empty but the sum can be 0 then for all j==0 t[i][j]=0

Now if the value of the element is more than the target sum we reject it.

While if the value of the element is less than or equal to the target sum then we will have a choice either to include it or not. Here we will also see all the cases till the end(unlike subset-sum in which if we found out the subset with equal sum we return true). It may be possible that more than one pair exists in the subset and we have to return that count.

So for that reason, we will cover all choices and we will use the + operator instead of ||. (One reason for using + is also we are now dealing with int data type not boolean.)

At last, we will return the last cell of the matrix which will give us the output of the count of all the subsets with the given sum.

(Here we are also taking modulus with 1000000007 because the input is very large and storing such large values in an int array is not suitable. So every time when we value of element less than, more than, or equal to(arr[i-1] at this instance) the target sum(j at this instance)then we store the value by taking its modulus with 1000000007.

And while returning too we return value with the modulus so as to avoid overflow conditions.)

Time:O(N*SUM)[Gfg Time: 0.4/8.1]

SPACE:O(N*SUM)

Thanks for Reading.😇