Count SubsetSum Problem [ Dynamic Programming ]

Problem Statement:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Given an array arr[] of length N and an integer X, the task is to find the number of subsets with a sum equal to X.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Here is my solution to the given problem:

Prerequisites: 0/1 Knapsack Problem

Solution :

A simple approach is to solve this problem by generating all the possible subsets and then checking whether the subset has the required sum. This approach will have exponential time complexity. However, for smaller values of SUM and array elements, this problem can be solved using dynamic programming.

Using Tabulation Method

Constraint: Array will always have positive elements

class Solution{
public int perfectSum(int arr[],int n, int sum){ 
 if(n==0){
    return 0;
 }
 
 int t[][] = new int[n+1][sum+1];
 
 for(int i=0;i<sum+1;i++){
     t[0][i] = 0;
 }
 for(int i=0;i<n+1;i++){
     t[i][0] = 1;
 }
 
 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] + t[i-1][j-arr[i-1]])%1000000007; 
    }
    else{
      t[i][j] = t[i-1][j]%1000000007;
    }
  }
}
 
   return t[n][sum]%1000000007;
 } 
}

Time Complexity: O(sum*n), where the sum is the ‘target sum’ and ’n’ is the size of the array.

Auxiliary Space: O(sum*n), as the size of the 2-D array, is sum*n.

Same approach as 0/1 Knapsack and SubsetSum.

LinkedIn : [@rohitm17]