DSA interview question

Subset Sum Equal to Target

Hard · Algorithms · Topics: dynamic programming, knapsack

The problem

You're working on a billing reconciliation system for a fintech company. A customer disputes a charge on their statement, claiming it's a combination of smaller transactions that should sum up to a specific refund amount. You're given a list of transaction amounts (all non-negative) and a target amount. Your job: determine whether any subset of these transactions sums up exactly to the target — so the finance team can validate the dispute.

Example: transactions [4, 3, 9, 6], target 13 → Yes, because 4 + 9 = 13 or 4 + 3 + 6 = 13.

Function signature

bool subsetSumExists(vector<int>& arr, int target);

Test cases

Input `arr`	Target	Output	Explanation
`[3, 34, 4, 12, 5, 2]`	9	`true`	`4 + 5 = 9`
`[3, 34, 4, 12, 5, 2]`	30	`false`	No subset sums to 30
`[1, 2, 3]`	0	`true`	Empty subset sums to 0
`[]`	0	`true`	Empty array, empty subset sums to 0
`[]`	5	`false`	No elements to pick from
`[5]`	5	`true`	Single element equals target
`[1, 1, 1, 1]`	4	`true`	All four elements sum to target

(Standard assumption: all elements are non-negative integers, since subset sum with negatives changes the DP approach entirely.)

How interviewers phrase it

"Given an array of positive integers and a target sum, determine if there's a subset whose elements add up to the target."
"Can you partition this array into two subsets with equal sum?" (this is a variant built directly on top of subset sum — recognize the connection).
"Given coins/weights, can you make exactly this amount?" (disguised as coin/knapsack framing).

Clarifying questions to ask

Can the array contain negative numbers or zero? (Classic DP subset-sum assumes non-negative; negatives require a different technique — shifting indices or meet-in-the-middle.)
Do I need to just return true/false, or also which elements form the subset?
What's the range of target and array size n? (This determines if O(n × target) DP is feasible — if target is huge, e.g. 1e9, DP on sum won't work and you'd need meet-in-the-middle or subset generation.)
Can elements be reused (unbounded knapsack) or used at most once (0/1 knapsack)? — this problem is 0/1.
Are duplicates allowed in the array?

Follow-ups to expect

"Can you optimize space?"
"Can you also return the actual subset, not just true/false?"
"What if the target or array values are very large (e.g., up to 1e9)?"
"Partition Equal Subset Sum" (LeetCode 416)
"Count the number of subsets with sum equal to target"
"What if repetition of elements is allowed (unbounded)?"
"Minimum subset sum difference"

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