mediumDynamic Programming 1DPure DSA~25 min
Count Sign Assignments Reaching a Target
Each measurement may be added or subtracted from a running total. Count how many ways to assign plus and minus signs across all measurements so the total equals a given target.
Problem
Given an integer array nums and an integer target, assign a '+' or '-' to each element and concatenate, then count the assignments whose signed sum equals target. Return that count.
Input
An integer array nums of non-negative integers and an integer target.
Output
An integer: the number of sign assignments yielding target.
Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000; -1000 <= target <= 1000
Examples
Example 1
Input
nums = [1,1,1,1,1], target = 3
Output
5
Five sign patterns give a sum of 3.
Example 2
Input
nums = [1], target = 1
Output
1
Only +1.