Partitions with Given Difference

This is a classic DP subset-sum transformation problem.

Problem Summary

You are given:

• An array arr[]

• A difference diff

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

• If (totalSum + diff) is odd → return 0

• If diff > totalSum → return 0

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:

• dp[i][j] = number of ways to form sum j using first i elements

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:

• [6, 4]

Output

1

Complexity

• Time Complexity: O(n × sum)

• Space Complexity: O(sum)

Key Takeaways

• Convert partition problem → subset sum

• Always use:

S1 = (totalSum + diff) / 2

• Then count subsets with target sum

• Classic DP subset counting pattern

Pattern Recognition

If you see:

• partition into 2 subsets

• difference given

• count ways

Think instantly:

Subset Sum Transformation DP