PPractick

The problem

You're building a "fair team split" tool for a company hackathon. Given an array of employee "skill scores," you need to divide everyone into exactly two teams such that the total skill sums of the two teams are as close to equal as possible — minimizing unfairness. Given an array arr, partition it into two subsets S1 and S2 (every element goes to exactly one side) such that |sum(S1) - sum(S2)| is minimized. Return that minimum possible absolute difference.

Function signature

int minSubsetSumDifference(vector<int>& arr);

Test cases

arr	Output	Explanation
[1,6,11,5]	1	{1,5,6} sum=12 vs {11} sum=11 → difference 1
[1,2,3,9]	3	{1,2,3} sum=6 vs {9} sum=9 → difference 3
[1,2,3,4,5]	1	{1,2,3,4}... verify: totalSum=15, closest half is 7 or 8 → e.g. {2,5}=7 vs {1,3,4}=8 → diff 1
[1,3,100,4]	92	100 is so large it dominates; best split isolates it: {100} vs {1,3,4}=8 → diff 92
[5]	5	only one element, forced split: {5} vs {} → diff 5
[]	0	empty array → both sides empty, difference 0
[10,10]	0	perfectly balanced split: {10} vs {10}

(Note: no "target K" is given upfront here, unlike Count Subsets with Sum K — you must SEARCH over all achievable subset sums to find the one closest to totalSum/2. This is the key structural difference from earlier problems in this family.)

How interviewers phrase it

• "Partition this array into two subsets such that the absolute difference between their sums is minimized. Return that minimum difference."
• "Split these numbers into two groups as evenly as possible — what's the smallest possible imbalance?"
• Frequently the capstone problem in the subset-sum DP family, often asked right after Count Subsets with Sum K, specifically to test whether you can extend a "check one specific K" DP into a "search over all achievable K" DP.

Clarifying questions to ask

1. Must every element go to exactly one of the two groups (a true partition), or can elements be excluded? (Standard: every element assigned, no exclusions.)
2. Are array elements guaranteed non-negative? (Standard assumption — affects the DP capacity range.)
3. Is an empty group allowed (i.e., can one "subset" have zero elements)? (Yes, typically — e.g., a single-element array trivially forces one empty side.)
4. What's the expected range of element values and array size? (Signals the feasible capacity for the underlying subset-sum DP — total sum could be large, affecting DP table size.)
5. Do I need to return just the minimum difference, or also which elements go into each group?

Follow-ups to expect

1. "How does this build on 'Count Subsets with Sum K'?"
2. "Do you need the counting variant of subset-sum, or just reachability (yes/no)?"
3. "Can you optimize space?"
4. "Why do you only need to search sums up to totalSum / 2, not the full range?"
5. "Can you reconstruct which elements go into each optimal subset?"
6. "What if you needed to partition into K > 2 balanced groups?"

Related questions

• Subset sum equal to target Hard
• Partition equal subset sum Hard
• Count subsets with sum K Hard
• Count partitions with given difference Hard
• Target sum Hard
• Minimum Coins Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in