Count partitions with given difference

Return the Count partitions with given difference

Partition Array with a Given Difference

Problem Statement

Given an array, arr, of n integers and an integer diff, count the number of ways to split the array into two subsets, S1 and S2, such that:

• |sum(S1) - sum(S2)| = diff
• sum(S1) ≥ sum(S2)

A partition means that S1 and S2 together make up the entire original array — every element belongs to exactly one of the two subsets, with none left out and none used twice.

Return the result modulo 10⁹ + 7.

Examples

Example 1

Input: arr = [1, 1, 2, 3], diff = 1

Output: 3

Explanation: The valid subset pairs are: [1, 2] and [1, 3]; [1, 3] and [1, 2]; and [1, 1, 2] and [3].

Example 2

Input: arr = [1, 2, 3, 4], diff = 2

Output: 2

Explanation: The valid subset pairs are: [1, 3] and [2, 4]; and [1, 2, 3] and [4].

Solution 1: Direct Recursion, Tracking Both Subset Sums

This approach directly follows the problem description: for every element, we decide whether it goes into S1 or S2, tracking both subset sums (w1 and w2) as we go. Once every element has been placed, we check whether the final difference matches diff.

We use a Map to memoize results, keyed by a combination of the current index and both running sums, so we don't repeat the same calculation twice.

countPartitions(n, diff, arr) {
    let dp = new Map();

    function recurr(index, w1, w2) {
        let key = `${index}#${w1}#${w2}`;

        if (index === n) {
            return w1 - w2 === diff ? 1 : 0;
        }

        if (dp.has(key)) {
            return dp.get(key);
        }

        const currWeight = arr[index];

        let pickw1 = recurr(index + 1, w1 + currWeight, w2);
        let pickw2 = recurr(index + 1, w1, w2 + currWeight);

        let result = (pickw1 + pickw2) % 1000000007;

        dp.set(key, result);

        return result;
    }

    return recurr(0, 0, 0);
}

This is a very direct, intuitive way to solve the problem. However, since the cache key depends on the running sums themselves (not just a single target), the number of distinct states it needs to track can grow quite large for bigger arrays, making it less efficient than the next approach.

Solution 2: Reframe as "Count Subsets Summing to a Target"

There's a well-known trick to make this problem much more efficient: instead of tracking both subset sums separately, we can turn it into a single subset-sum counting problem.

If totalSum is the sum of the whole array, and we want sum(S1) - sum(S2) = diff, then with a bit of algebra:

• sum(S1) + sum(S2) = totalSum
• sum(S1) - sum(S2) = diff

Adding these two equations together gives: 2 * sum(S1) = totalSum + diff, so sum(S1) = (totalSum + diff) / 2.

Equivalently, this solution calculates the target for the smaller subset: target = (totalSum - diff) / 2, and counts how many subsets of arr sum up to exactly that target.

• If totalSum - diff is negative, or not evenly divisible by 2, there's no valid way to split the array this way, so we return 0 immediately.

function countPartitions(arr, d) {
  const totalSum = arr.reduce((a, b) => a + b, 0);

  // Edge cases mentioned at 11:48-12:10
  if (totalSum - d < 0 || (totalSum - d) % 2 !== 0) return 0;

  const target = (totalSum - d) / 2;
  const n = arr.length;

  // Initialize DP table with -1
  const dp = Array.from({ length: n }, () => Array(target + 1).fill(-1));
  const MOD = 1e9 + 7;

  function solve(idx, currentTarget) {
    // Base cases (14:12-15:00)
    if (idx === 0) {
      if (currentTarget === 0 && arr[0] === 0) return 2;
      if (currentTarget === 0 || currentTarget === arr[0]) return 1;
      return 0;
    }

    if (dp[idx][currentTarget] !== -1) return dp[idx][currentTarget];

    let notTake = solve(idx - 1, currentTarget);
    let take = 0;
    if (arr[idx] <= currentTarget) {
      take = solve(idx - 1, currentTarget - arr[idx]);
    }

    return (dp[idx][currentTarget] = (take + notTake) % MOD);
  }

  return solve(n - 1, target);
}

Note: The base case at idx === 0 has a special rule: if the target is 0 and the first element itself is 0, it returns 2. This handles a subtle edge case — when an element's value is 0, there are actually two distinct ways to reach a sum of 0 using it: either by including it (since adding 0 doesn't change the sum) or by excluding it. Both count as separate, valid selections.

Solution 3: Tabulation (Space-Optimized)

This is the bottom-up version of Solution 2, using the classic "0/1 knapsack" style subset-sum counting technique, with a single 1D array instead of a 2D grid.

• dp[j] represents the number of ways to form a sum of j using the elements processed so far.
• We start with dp[0] = 1, since there's always exactly one way to make a sum of 0 — by picking nothing.
• For each element in the array, we update dp from right to left (from target down to arr[i]). This ensures we don't accidentally use the same element more than once within a single pass.

function countPartitions(arr, d) {
  const n = arr.length;
  const totalSum = arr.reduce((acc, curr) => acc + curr, 0);

  // Edge cases: totalSum - d must be >= 0 and even
  if (totalSum - d < 0 || (totalSum - d) % 2 !== 0) {
    return 0;
  }

  const target = (totalSum - d) / 2;
  const MOD = 1e9 + 7;

  // Standard DP array approach for subset sum count
  let dp = new Array(target + 1).fill(0);

  // Base case: empty subset sum is 0 (one way)
  dp[0] = 1;

  for (let i = 0; i < n; i++) {
    for (let j = target; j >= arr[i]; j--) {
      dp[j] = (dp[j] + dp[j - arr[i]]) % MOD;
    }
  }

  return dp[target];
}