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

Sharing Is Caring...

## Comments :

## Post a Comment