Count Partitions with Given Difference

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMorgan StanleyWalmart

Given an array of non-negative integers and a target difference, count how many ways the array can be split into two groups — every element assigned to exactly one of the two — such that the first group's sum minus the second group's sum equals exactly that target difference. If the two group sums are called S1 and S2, then S1 - S2 equals the target difference and S1 + S2 equals the array's total, which pins S2 down to one fixed value the moment the total and target are known. That turns the question into counting how many subsets of the array sum to exactly that fixed value — the same counting search as Count Subsets with Sum K, just with the target computed from the total and the desired difference first.

Test Case 1:

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

Output:3

Explanation:Three ways split the array into groups whose sums differ by exactly 2: {3}|{2,2,1} (3 vs 5), {2,1}|{2,3} — twice, once for each 2 — (3 vs 5).

Test Case 2:

Input:nums = [5, 2, 6, 4], diff = 3

Output:1

Explanation:Only {2,6}|{5,4} splits the array with a difference of 3 (8 vs 9).

Test Case 3:

Input:nums = [1, 1, 1, 1], diff = 0

Output:6

Explanation:Choosing any 2 of the four 1s for group 1 (and the other 2 for group 2) gives a difference of 0 — C(4,2) = 6 ways.

Constraints

◆1 ≤ nums.length ≤ 20
◆0 ≤ nums[i] ≤ 100
◆0 ≤ diff ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Every number is assigned to one of two groups, so track only the running sum of the first group as each number is included in it or left for the second — the second group's sum is always the total minus that. Once every number has been assigned, this particular way of splitting counts as valid only if the two group sums actually differ by exactly the target amount. Both choices are explored at every number, since either could be part of a valid split, and the total count is the number of leaves across the whole recursion where that exact difference was achieved.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;
    private int total;
    private int diff;

    public int countPartitionsWithDiff(int[] nums, int diff) {
        this.nums = nums;
        this.diff = diff;
        int total = 0;
        for (int num : nums) total += num;
        this.total = total;
        return solve(0, 0);
    }

    private int solve(int i, int sum1) {
        if (i == nums.length) return (2 * sum1 - total == diff) ? 1 : 0;
        return solve(i + 1, sum1 + nums[i]) + solve(i + 1, sum1);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

If the two groups' sums are called S1 and S2 with S1 - S2 = diff and S1 + S2 = total, then S2 works out to exactly (total - diff) ⁄ 2 — a fixed target the moment the total and diff are known. That target has to be a non-negative whole number for any valid split to exist at all; if (total - diff) is odd or negative, there's no way to hit it and the answer is immediately 0. Otherwise, the question becomes exactly Count Subsets with Sum K for that target: track, for every amount up to it, how many subsets of the numbers seen so far reach it exactly, sweeping each number's contribution in from the target down to that number's own value. The count at the target once every number has been swept through is the answer.

TimeO(n × sum)

SpaceO(sum)