This is a classic DP subset-sum transformation problem.

Problem Summary

You are given:

You need to count:

Number of ways to split array into two subsets S1 and S2 such that:

sum(S1) - sum(S2) = diff

Key Insight (VERY IMPORTANT)

Let:

S1 + S2 = totalSum
S1 - S2 = diff

Add both equations:

2 * S1 = totalSum + diff
S1 = (totalSum + diff) / 2

Problem reduces to

Find number of subsets with sum:

target = (totalSum + diff) / 2

Edge Cases

Intuition

We are NOT directly splitting into two sets.

Instead:

We count subsets with a fixed sum = target

DP Idea (Subset Count Problem)

We use:

Transition

For each element:

include + exclude

Java Solution (Space Optimized DP)

class Solution {
    public int countPartitions(int[] arr, int diff) {
        int n = arr.length;

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

        // check feasibility
        if ((totalSum + diff) % 2 != 0 || totalSum < diff) {
            return 0;
        }

        int target = (totalSum + diff) / 2;

        int[] dp = new int[target + 1];

        dp[0] = 1;

        for (int num : arr) {
            for (int j = target; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[target];
    }
}

Example Walkthrough

Input

arr = [5, 2, 6, 4], diff = 3

Step 1: total sum

total = 17

Step 2: target

(17 + 3) / 2 = 10

Step 3: count subsets with sum = 10

Valid subsets:

Output

1

Complexity

Key Takeaways

S1 = (totalSum + diff) / 2

Pattern Recognition

If you see:

Think instantly:

Subset Sum Transformation DP