Target Sum

MediumDynamic Programming0/1 knapsack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array of non-negative integers nums and an integer target. You must place exactly one of the two symbols '+' or '-' in front of every element of nums, then concatenate the signed values into a single arithmetic expression and evaluate it. For example, given nums = [3, 1] you could form +3 -1 = 2 or -3 -1 = -4, among others. Return the number of distinct sign assignments that make the resulting expression evaluate to exactly target. Two assignments are considered different if any single element is given a different sign, even when two elements happen to share the same value.

Examples

Input: nums = [1,1,1,1,1], target = 3
Output: 5
There are five ways to assign signs so the sum is 3. One example is -1 +1 +1 +1 +1 = 3; flipping which single element gets the minus sign gives the other four ways.
Input: nums = [1], target = 1
Output: 1
Only +1 reaches the target. -1 gives -1, so exactly one assignment works.
Input: nums = [1], target = 2
Output: 0
The single element can only produce +1 or -1, so the target 2 is unreachable.

Constraints

  • `1 <= nums.length <= 20`
  • `0 <= nums[i] <= 1000`
  • `0 <= sum(nums) <= 1000`
  • `-1000 <= target <= 1000`
  • The answer is guaranteed to fit in a 32-bit signed integer.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 0/1 knapsack problems