Standard Bar Dynamic Programming · DP on Subsequences O(n*S) · O(S)
A calibration rig flips each of n sensor channels into either an amplifying or an attenuating mode before a measurement run. The lab needs the combined gain to land exactly on a target offset, and the technician counts how many switch assignments achieve it. Channels with identical ratings are still independent hardware, so each assignment counts separately.
Input: An array nums of n non-negative integers and an integer target.
Output: Return the number of ways to assign + or - signs so the signed sum equals target.
1 <= n <= 200 <= nums[i] <= 1000sum of nums <= 1000-1000 <= target <= 1000Input: {"nums":[1,1,1,1,1],"target":3}
Output: 5
Exactly one channel attenuates (five choices); each gives 4 - 1 = 3.
Input: {"nums":[1],"target":1}
Output: 1
The single channel must amplify: +1.