Minimum subset sum difference

Problem Link

Partition a Set into Two Subsets with Minimum Difference

Problem Statement

Given an array arr[] of size N, the task is to partition it into two subsets such that the absolute difference of their subset sums is minimized.

Return the minimum absolute difference.

Examples

Input: arr[] = {1, 6, 11, 5}
Output: 1
Explanation: Subset1 = {1, 5, 6} = 12; Subset2 = {11} = 11; |12 - 11| = 1

Input: arr[] = {36, 7, 46, 40}
Output: 23

Constraints

• 1 <= N <= 100

• 1 <= arr[i] <= 100

Intuition + Choice Diagram

We aim to split the array into two subsets S1 and S2 such that:

|sum(S1) - sum(S2)| is minimized

Since total sum = S = sum of all elements, we try to find all possible subset sums up to S/2 and pick the one that gives minimum difference.

Choice Diagram:

At each index, we have 2 choices:

        f(i, target)
         /       \
  Pick arr[i]   Skip arr[i]
f(i-1, target-arr[i])   f(i-1, target)

IBH Method for Recursion

• Induction: At index i, with target sum = sum, check if this sum is possible using elements 0..i.

• Base Case:

  • If target == 0 → return true

  • If index == 0 → return arr[0] == target

• Hypothesis: Assume the subproblems work.

• Build: Use pick / not pick logic to construct the result.

Approach 1: Recursion (Top Down with IBH)

public class Solution {
    public static boolean isSubsetPossible(int index, int target, int[] arr) {
        if (target == 0) return true;
        if (index == 0) return arr[0] == target;

        boolean notPick = isSubsetPossible(index - 1, target, arr);
        boolean pick = false;
        if (arr[index] <= target) {
            pick = isSubsetPossible(index - 1, target - arr[index], arr);
        }

        return pick || notPick;
    }

    public static int minSubsetSumDifference(int[] arr, int n) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;

        int minDiff = Integer.MAX_VALUE;
        for (int s1 = 0; s1 <= totalSum / 2; s1++) {
            if (isSubsetPossible(n - 1, s1, arr)) {
                int s2 = totalSum - s1;
                minDiff = Math.min(minDiff, Math.abs(s2 - s1));
            }
        }

        return minDiff;
    }
}

Approach 2: Memoization

public class Solution {
    public static int minSubsetSumDifference(int[] arr, int n) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;

        Boolean[][] dp = new Boolean[n][totalSum + 1];

        for (int i = 0; i < n; i++)
            for (int j = 0; j <= totalSum; j++)
                dp[i][j] = null;

        for (int s1 = 0; s1 <= totalSum / 2; s1++) {
            if (isSubsetPossible(n - 1, s1, arr, dp)) {
                int s2 = totalSum - s1;
                return Math.min(Math.abs(s2 - s1), Math.abs(s1 - s2));
            }
        }

        return 0;
    }

    public static boolean isSubsetPossible(int i, int target, int[] arr, Boolean[][] dp) {
        if (target == 0) return true;
        if (i == 0) return arr[0] == target;

        if (dp[i][target] != null) return dp[i][target];

        boolean notPick = isSubsetPossible(i - 1, target, arr, dp);
        boolean pick = false;
        if (arr[i] <= target)
            pick = isSubsetPossible(i - 1, target - arr[i], arr, dp);

        return dp[i][target] = pick || notPick;
    }
}

Approach 3: Tabulation

public class Solution {
    public static int minSubsetSumDifference(int[] arr, int n) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;

        boolean[][] dp = new boolean[n][totalSum + 1];

        for (int i = 0; i < n; i++) dp[i][0] = true;
        if (arr[0] <= totalSum) dp[0][arr[0]] = true;

        for (int i = 1; i < n; i++) {
            for (int target = 1; target <= totalSum; target++) {
                boolean notPick = dp[i - 1][target];
                boolean pick = false;
                if (arr[i] <= target) {
                    pick = dp[i - 1][target - arr[i]];
                }
                dp[i][target] = pick || notPick;
            }
        }

        int minDiff = Integer.MAX_VALUE;
        for (int s1 = 0; s1 <= totalSum / 2; s1++) {
            if (dp[n - 1][s1]) {
                int s2 = totalSum - s1;
                minDiff = Math.min(minDiff, Math.abs(s2 - s1));
            }
        }

        return minDiff;
    }
}

Approach 4: Space Optimization

public class Solution {
    public static int minSubsetSumDifference(int[] arr, int n) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;

        boolean[] prev = new boolean[totalSum + 1];
        prev[0] = true;
        if (arr[0] <= totalSum) prev[arr[0]] = true;

        for (int i = 1; i < n; i++) {
            boolean[] curr = new boolean[totalSum + 1];
            curr[0] = true;
            for (int target = 1; target <= totalSum; target++) {
                boolean notPick = prev[target];
                boolean pick = false;
                if (arr[i] <= target) {
                    pick = prev[target - arr[i]];
                }
                curr[target] = pick || notPick;
            }
            prev = curr;
        }

        int minDiff = Integer.MAX_VALUE;
        for (int s1 = 0; s1 <= totalSum / 2; s1++) {
            if (prev[s1]) {
                int s2 = totalSum - s1;
                minDiff = Math.min(minDiff, Math.abs(s2 - s1));
            }
        }

        return minDiff;
    }
}

Time and Space Complexities

Dry Run

For arr = [1, 6, 11, 5], total = 23
Check all sums s1 = 0 to 11 where subset possible → pick the one with |s1 - (23-s1)| minimum.

At s1 = 11, s2 = 12 → minDiff = 1

Conclusion

This is a classic variation of subset sum problem and a base for many DP questions, like:

• Equal Partition

• Count of Subsets with Given Sum

• Target Sum, etc.

Mastering this helps in understanding DP on subsets.