Target Sum

Choose one plus or minus sign for every position of nums so the signed sum equals target. Count sign assignments modulo 1,000,000,007. Positions are distinct,…

Choose one plus or minus sign for every position of nums so the signed sum equals target. Count sign assignments modulo 1,000,000,007. Positions are distinct, and +0 and -0 are different assignments. Negative targets are valid.

- 1 <= n <= 100; 0 <= nums[i] <= 1000; sum(nums) <= 10000. - -1000 <= target <= 1000. - Visualization accepts at most 6 items and transformed capacity at most 10; larger valid inputs are coding-only. Infeasible range/parity cases terminate before table allocation.

Example 1: input values = [0,0,1], target = 1; output 4. The two zero positions each have two distinct choices, multiplying the one feasible assignment by four.

Example 2: input values = [1,2,3], target = -2; output 1. The only assignment is -1 + 2 - 3 = -2. Negative requested targets are valid.

Example 3: input values = [1,1], target = 0; output 2. The two assignments are +1 - 1 and -1 + 1. The equal-valued positions still receive signs independently.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.