DSA interview question

Check If a Subsequence with Sum K Exists

Easy · Algorithms · Topics: recursion, backtracking

The problem

A vending machine that only takes exact change holds a list of coins, each coin usable once. Given a price K, can some subset of the coins add up to exactly K? This is the classic subset-sum decision problem. The recursion is the pick/skip pattern that stops at the first success: return true the moment the running sum reaches K, and never explore further once any branch has succeeded. Because the state is just (index, sum), the recursion also turns into an O(n · K) boolean table.

Example: [3, 34, 4, 12, 5, 2], K = 9 → true (4 + 5).

Function signature

bool isSubsetSum(const vector<int>& arr, int k);  // non-negative values

Test cases

Input `(arr, K)`	Output	Explanation
`([3, 34, 4, 12, 5, 2], 9)`	`true`	4 + 5 (or 3 + 4 + 2)
`([3, 34, 4, 12, 5, 2], 30)`	`false`	Everything except 34 only sums to 26
`([1, 2, 3], 6)`	`true`	All three
`([2, 4, 6], 5)`	`false`	Only even sums are possible
`([8], 8)`	`true`

(Confirm: each element can be used at most once; values are non-negative; K = 0 is always reachable with the empty subset.)

How interviewers phrase it

"Given an array of non-negative integers and a value sum, determine if there's a subset with sum equal to the given sum" (GeeksforGeeks "Subset Sum Problem").
It's the "find just one" version of the subsequence patterns.

Clarifying questions to ask

Can elements be reused? (No.)
Can values be negative? (No, which allows pruning and a bounded table.)
How large are n and K? (That decides between recursion and DP.)

Follow-ups to expect

"How do you stop early?"
"Why can you return as soon as sum == K here, but not when counting?"
"How do you make it polynomial?"
"Can it be faster?"
"Complexity?"

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