Two Subset with minimum Difference

Two Subset with minimum Difference

  February 21, 2018    

---

Recursive approach is to calculate sum and check for min diff every time by including element and not including(include in set 2).

This will take exponential time.

Another approach is to use concept of knapsack with capacity of sum/2 and will get maximum sum of a subset.

Approach Used by me is to use SUBSET sum problem and check for closest sum to sum/2 and subtract it from total sum hence will get sum of both sets then print diff.


Code:

public static int sum(int n,int arr[])
{
     int asum=0;
     for(int i=0;i<n;++i)
     asum+=arr[i];
// s[i][j] represents sum j till  n numbers
boolean s[][]=new boolean[n+1][asum+1];
for(int i=0;i<=n;++i)
s[i][0]=true;
for(int i=1;i<=n;++i)
for(int j=1;j<=asum;++j)
{
     s[i][j]=s[i-1][j];
     if(j>=arr[i-1])
     s[i][j]|=s[i-1][j-arr[i-1]];
}
//return s[n][asum]?1:0;
for(int i=asum/2;i<=asum;++i)
{
     if(s[n][i]){
         // System.out.println(i+" "+asum);
//asum-2*i is used as sum of 1 set is i and another is asum-i , subtract sum of subset
     return Math.abs(asum-2*i);}
}
return 0;
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(sum(n,arr));
}
}