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)
        );

    }

}