Partitions with Given Difference | Optimal Solution

Given an array arr[], partition it into two subsets(possibly empty) such that each element must belong to only one subset. Let the sum of the elements of these two subsets be sum1 and sum2. Given a difference d, count the number of partitions in which sum1 is greater than or equal to sum2 and the difference between sum1 and sum2 is equal to d. 

Here’s the [Problem Link] to begin with.

Examples :

Input: arr[] =  [5, 2, 6, 4], d = 3
Output: 1
Explanation: There is only one possible partition of this array. Partition : {6, 4}, {5, 2}. The subset difference between subset sum is: (6 + 4) - (5 + 2) = 3.

Input: arr[] = [1, 1, 1, 1], d = 0 
Output: 6 
Explanation: We can choose two 1's from indices {0,1}, {0,2}, {0,3}, {1,2}, {1,3}, {2,3} and put them in sum1 and remaning two 1's in sum2.
Thus there are total 6 ways for partition the array arr. 

Input: arr[] = [1, 2, 1, 0, 1, 3, 3], d = 11
Output: 2

Constraint:
1 <= arr.size() <= 50
0 <= d  <= 50
0 <= arr[i] <= 6

Problem-to-Subset-Sum Reduction

Given an array arr, split it into two subsets S1 and S2 such that:

• sum(S1) − sum(S2) = d
• Let total = sum(arr), and let s1 = sum(S1).
• Since s1 + s2 = total and s1 − s2 = d, solving these gives s1 = (total − d)/2.

Therefore, counting the number of valid partitions with difference d is equivalent to counting the number of subsets with sum exactly (total − d)/2, provided that:

• (total − d) ≥ 0
• (total − d) is even

If either fails, the answer is 0.

This is exactly where the Perfect Sum DP (count of subsets equal to a target) plugs in.

How to Modify the Previous “Perfect Sum” Solution

1. Compute total = sum(arr).
2. Validate feasibility:
   • If (total − d) < 0 or (total − d) is odd, return 0.
3. Set target = (total − d) // 2.
4. Return count of subsets equal to target using the same Perfect Sum DP (with careful zero handling).

This reuses the exact counting DP from Perfect Sum, including the special initialization when zeros appear (since zeros double the number of ways to achieve sum 0 at that position).

Space-Optimized Counting DP (Reused as-is)

• prev[t] stores the count of subsets from the processed prefix that sum to t.
• Handle arr carefully:
  • If arr == 0: prev = 2 (pick or not-pick both keep sum 0).
  • Else prev = 1, and if arr ≤ target then prev[arr] = 1.
• Transition for each element:
  • pick = prev[t − arr[i]] if arr[i] ≤ t else 0
  • not_pick = prev[t]
  • curr[t] = pick + not_pick

This is exactly the logic from the Perfect Sum Problem.

Complete Code

class Solution:
    def perfectSum(self, arr, target):
        n = len(arr)
        prev = [0 for _ in range(0, target + 1)]
        # Base init for index 0 with zero handling
        if arr == 0:
            prev = 2
        else:
            prev = 1
            if arr <= target:
                prev[arr] = 1
        # Rolling 1D DP for counts
        for index in range(1, n):
            curr = [0 for _ in range(0, target + 1)]
            for total in range(0, target + 1):
                if arr[index] > total:
                    pick = 0
                else:
                    pick = prev[total - arr[index]]
                not_pick = prev[total]
                curr[total] = pick + not_pick
            prev = curr
        return prev[target]

    def countPartitions(self, arr, d):
        n = len(arr)
        total = sum(arr)
        # Feasibility check for target = (total - d) / 2
        if (total - d) < 0 or (total - d) % 2 == 1:
            return 0
        return self.perfectSum(arr, (total - d) // 2)

Notes and Edge Cases

• Zeros in arr: Already handled by the Perfect Sum initialization (prev = 2 when arr == 0), which is crucial for accurate counting.
• Large counts: If the platform requires modulo (e.g., 1e9+7), wrap additions in modulo at each DP update; your current function returns raw counts.
• Non-negative integers: The reduction assumes non-negative inputs, consistent with Perfect Sum assumptions.

Takeaway

“Partitions with Given Difference” is just the Perfect Sum Problem in disguise: compute target = (total − d)/2 and count subsets with that sum using the same DP. This small transformation unlocks a clean, efficient, and reusable solution.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.