Subset Sum Problem | Dynamic Problem

Hello Guys, Today we will solve a very interesting problem which is Subset Sum Problem. This is a DP based problem.

In this question, you have one array which contains some element and the total sum is given to you. You have to find a subset which is equal to a given sum. You have to print output True or False. 

Example:  

arr[ ]={2,3,7,8,10};

sum=11;

We have to find the subset which is equal to the given sum which is 11. 

Solution:

I take a fixed array element or value of the sum. You can take input in runtime.

int n=5;
int a[]={2,3,7,8,10}; //Array elements
int sum=11;  //Given Sum
//create a 2D boolean array with size of n+1 and sum+1
boolean[][] t=new boolean[n+1][sum+1]; 

for(int i=0;i<n+1;i++)
{
    for(int j=0;j<sum+1;j++)
    {
        if(i==0&&j==0)
        {
            t[i][j]=true;
        }
        else if(i==0)
        {
            t[i][j]=false;
        }
        else if(j==0)
        {
            t[i][j]=true;
        }
        else
        {
        if(a[i-1]<=j)
        {
            t[i][j]=Boolean.logicalOr((t[i-1][j-a[i-1]]),t[i-1][j]);
        }
        else
        {
            t[i][j]=t[i-1][j];
        }
        }
    }
}
System.out.println(t[n][sum]);

Output: true;

Others Coding Problems:

Caesar Cipher HackerRank Solution In Java.

Super Reduced String Hackerrank Solution In Java.

Sharing Is Caring...