DSA interview question

Target Sum

Hard · Algorithms · Topics: dynamic programming, knapsack

The problem

You're building a "portfolio scenario counter" for a trading-simulation tool. Each entry in an array nums represents a trade's magnitude, but every trade could have gone either long (+) or short (-) — the historical direction wasn't logged, only the magnitudes. Given the array nums and a known final net target, your job is to count how many distinct sign assignments (one + or - per element) result in an expression that sums exactly to target. This tells the risk team how many plausible historical scenarios could explain the observed final outcome.

Function signature

int findTargetSumWays(vector<int>& nums, int target);

Test cases

`nums`	`target`	Output	Explanation
`[1,1,1,1,1]`	3	5	5 distinct sign assignments sum to 3 (e.g. +1+1+1+1-1, and 4 other permutations of one minus)
`[1]`	1	1	only `+1` works
`[1]`	2	0	impossible — max achievable magnitude is 1
`[0,0,0,0,0,0,0,0,1]`	1	256	each 0 can independently be + or - (no effect), giving 2^8 = 256 combinations, all valid
`[]`	0	1	empty array, target 0 → one way: the empty assignment
`[100]`	-100	1	only `-100` works
`[1,2,3]`	0	2	`+1+2-3` and `-1-2+3`

(Watch the [0,0,...,0,1] case — it's a classic trap testing whether your subset-sum reduction correctly handles zero-valued elements, which double the count of every valid subset they're added to.)

How interviewers phrase it

"Given an array of non-negative integers and a target, assign a + or - sign to each number so the sum equals target — count how many ways this is possible."
"How many ways can you insert + and - between these numbers to reach a given total?"
Sometimes disguised without mentioning DP at all, purely as a combinatorics/brute-force question first — they want to see you notice it's exponential (2^n sign assignments) before optimizing.

Clarifying questions to ask

Can array elements be 0? (Critical edge case — zeros don't affect the sum but still double the combinatorial count, since + and - both give 0.)
Are elements guaranteed non-negative? (Standard problem statement assumes nums[i] >= 0; the sign is what you're choosing, not an inherent property of the input.)
Can target be negative?
What's the expected size of nums and magnitude of values? (Signals whether brute-force 2^n recursion needs to become DP, and what capacity range the DP subset-sum table needs.)
Do I need to enumerate the actual sign assignments, or just count them?

Follow-ups to expect

"Can you reduce this to Subset Sum / 0-1 Knapsack?"
"What's the brute-force complexity, and why is it bad?"
"Can you optimize space?"
"What if elements could be negative in the input?"
"How does this compare to Partition Equal Subset Sum?"
"Can you solve it with pure recursion + memoization instead of converting to subset sum?"

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