Amit Gupta
1 min readNov 5, 2023

--

Given an array arr of size n containing non-negative integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

S1-S2 = MinDiff;

S1 = TotalSum(arr) -S2;

Hence We can say we have to find minimum value of equation :

Abs(TotalSum - 2 * S2)

class MinDiffSubset
{

public int minDifference(int arr[], int n)
{
if(arr == null || arr.length == 0) return -1;

int totalSum =0;
for(int x : arr){
totalSum+= x;
}

int[][]dp = new int[n][totalSum+1];
for(int[] row : dp){
Arrays.fill(row, -1);
}

return findMinDiff(arr, n, dp, totalSum, 0, 0);

}

public int findMinDiff(int[] arr, int n, int[][] dp, int totalSum, int index, int currentSum){

if(index == n-1){
return Math.abs(totalSum - 2*currentSum);
}

if(dp[index][currentSum] != -1) return dp[index][currentSum];

return dp[index][currentSum] = Math.min(findMinDiff(arr, n, dp, totalSum, index+1, currentSum + arr[index]),
findMinDiff(arr, n, dp, totalSum, index+1, currentSum)
);

}

}

--

--