DSA interview question

Count Partitions with Given Difference

Hard · Algorithms · Topics: dynamic programming, knapsack

The problem

You're building an "audit reconciliation" tool for a finance team. Given an array of transaction amounts, the array must be split into two groups — say S1 and S2 — such that every transaction belongs to exactly one group. The team wants to know: for a target discrepancy D, in how many distinct ways can the transactions be partitioned into two groups such that sum(S1) - sum(S2) = D? This surfaces every plausible way the ledger could have been split to produce that specific discrepancy.

Function signature

int countPartitions(vector<int>& arr, int D);

Test cases

`arr`	`D`	Output	Explanation
`[1,1,2,3]`	1	3	3 distinct partitions into (S1,S2) give a difference of 1
`[1,1,1,1]`	0	3	3 ways to split 2-and-2 such that both sides sum to 2
`[1,2,3,1]`	1	3	same multiset as first test, reordered — count should match structurally
`[1]`	1	1	S1={1}, S2={} → difference 1
`[]`	0	1	empty array, trivially one partition: both groups empty
`[5]`	10	0	impossible — max achievable difference is 5
`[0,0,1]`	1	4	zeros can go to either side freely, doubling valid combinations — classic trap case

(This is the "unsigned" sibling of Target Sum — instead of assigning +/- to a fixed array and hitting an exact target, you're partitioning into two groups with a difference constraint. The math reduction is nearly identical.)

How interviewers phrase it

"Given an array, count the number of ways to partition it into two subsets such that the difference between their sums equals D."
"Split this array into two groups so their sums differ by exactly D — how many ways can you do this?"
Frequently given as a direct follow-up right after Target Sum, specifically to test whether you notice the underlying reduction is essentially identical.

Clarifying questions to ask

Must every element belong to exactly one of the two groups (a true partition), or can elements be excluded entirely? (Standard: every element must go to one side or the other — it's a full partition, not a subset selection.)
Are array elements guaranteed non-negative? (Standard assumption; affects the sum-based reduction.)
Is D guaranteed non-negative? (Since sum(S1) - sum(S2) = D could be asked with either group being the "larger" one — usually D is given as non-negative, and by convention S1 is the larger-or-equal side.)
Can array elements be 0? (Important edge case — zeros can go to either side without affecting the sum difference, but still count as distinct partitions.)
What's the expected range of element values and array size? (Signals the capacity range for the underlying subset-sum DP.)

Follow-ups to expect

"How does this relate to Target Sum?"
"What's the feasibility check, and why is it needed?"
"Can you optimize space?"
"What if D could effectively be negative (i.e., either group could be the larger one)?"
"How would you handle multiple zero-valued elements correctly?"
"Can this be extended to partition into K groups with pairwise constraints?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview