Target Sum
Medium · 2-D Dynamic Programming
You are given a list of non-negative integers and a target integer. In front of each number you must place either a plus sign or a minus sign, then sum everything up. Count how many distinct ways of placing the signs make the total sum exactly equal to the target. Return that count.
Examples
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Why: There are exactly 5 ways to assign + or - signs to the numbers so they sum to 3.Input: nums = [1], target = 1
Output: 1
Why: Only the assignment +1 reaches the target.Input: nums = [1], target = 2
Output: 0
Why: No combination of +1 or -1 can ever equal 2.Constraints
1 <= nums.length <= 20, 0 <= nums[i] <= 1000, sum of nums[i] <= 1000, -1000 <= target <= 1000
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Target Sum. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.