Minimum Subset Sum Difference | Dynamic Problem.

Hello guys, Today we will solve an existing problem which is Minimum Subset Sum Difference. This is a DP based problem.  

In this question, we have given an array which contains some elements and we have to find the minimum difference of subsets. 

Example: 

arr[ ]={1,2,7};

The minimum difference of this question is 4. How?

Explanation:

In this question, we have to find 2 subsets which sum is equal to the sum of the whole array and the difference of 2 subsets is minimum. 

The subsets of the given array are {1,2},{7} because the sum of these 2 subsets is 10 and it is equal to the sum of a given array which is also 10 and the difference of these 2 arrays is minimum.

Solution:

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

int n=3;
int a[]={1,2,7,8};
int sum=0;

for(int i=0;i<a.length;i++)
{
    sum+=a[i];
}

boolean[][] t=new boolean[n+1][sum+1];
ArrayList<Integer> ar=new ArrayList<Integer>();
//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&&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]);
            
           // t[i][j]=Integer.sum((t[i-1][j-a[i-1]]),t[i-1][j]);
            
           
        }
        else
        {
            t[i][j]=t[i-1][j];
        }
        }
    }
}




    for(int l=0;l<(sum+1)/2;l++)
    {
        if(t[n][l]==true)
        {
            ar.add(l);
        }
    }

int min=Integer.MAX_VALUE;
for(int m=0;m<ar.size();m++)
{
    min=Integer.min(min,sum-2*(ar.get(m)));
}
System.out.println(min);
  

Solution: 4;

Others Coding Problems:

Caesar Cipher HackerRank Solution In Java.

Super Reduced String Hackerrank Solution In Java.

Subset Sum Problem | Dynamic Problem.