DSA interview question

Partition Equal Subset Sum

Hard · Algorithms · Topics: dynamic programming, knapsack

The problem

You're building a quick pre-check for the "fair team split" tool from the previous ticket — before running the full minimum-difference optimization, the product team wants a fast yes/no sanity check: can the given array of skill scores even be split into two teams with exactly equal total skill? Given an array arr, determine whether it can be partitioned into two subsets S1 and S2 such that sum(S1) == sum(S2).

Function signature

bool canPartition(vector<int>& arr);

Test cases

`arr`	Output	Explanation
`[1,5,11,5]`	true	{1,5,5} sum=11 vs {11} sum=11 — equal split exists
`[1,2,3,5]`	false	totalSum=11 is odd — equal split is impossible immediately
`[1,2,3,4,5,6,7]`	true	totalSum=28, need subset summing to 14 — e.g. {7,6,1} or {7,4,3}
`[2,2,3,5]`	false	totalSum=12, need subset summing to 6 — no combination hits exactly 6
`[1]`	false	single element, can't split into two non-trivial... actually check: totalSum=1 is odd → false
`[]`	true	empty array — both sides trivially empty and equal (sum 0 each)
`[0,0]`	true	totalSum=0 (even), subset {} or {0,0} both sum to 0 — trivially balanced

(First and cheapest check to always mention: if totalSum is odd, the answer is immediately false — no need to run any DP at all.)

How interviewers phrase it

"Given an array, determine if it can be split into two subsets with equal sum."
"Can you divide this array into two groups so both groups add up to the same total?"
Often the entry point to the entire subset-sum DP family — frequently followed immediately by "what if you also wanted the minimum difference instead of just yes/no?" (i.e., pivoting straight into the previous problem).

Clarifying questions to ask

Must both subsets be non-empty, or is an empty subset (paired with the full array) acceptable? (Standard convention: any valid partition counts, including trivial ones like an all-zero array splitting into {} and {0,0,...}.)
Are array elements guaranteed non-negative? (Standard assumption — needed for the DP capacity range to make sense.)
Could the array contain zero? (Doesn't break correctness, but worth confirming — zeros can go to either side freely.)
What's the expected range of array size and element magnitude? (Signals whether O(n × totalSum) DP capacity is feasible.)
Do you want just yes/no, or also one example of an equal-sum partition if it exists?

Follow-ups to expect

"What's the very first cheap check you should do before running any DP?"
"How does this relate to Count Subsets with Sum K / Minimum Subset Sum Difference?"
"Can you optimize space?"
"Can you reconstruct one valid partition, not just answer yes/no?"
"What if you wanted to check partition into K equal-sum groups, not just 2?"
"Can you solve this using bitset for a speed optimization?"

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