2-D Dynamic Programming Knapsack

550. Target Sum

You are given an array of non-negative integers nums and an integer target. Put a + or a - sign in front of every element, then add them all up.

Return the number of sign choices that add up to exactly target. Two choices are different if some element gets a different sign, even when the elements have equal values or are 0.

The number can be very large, so return it modulo 10⁹ + 7.

Example 1

Input: nums = [3, 1, 2, 2], target = 2

Output: 3

Explanation: +3 − 1 + 2 − 2, +3 − 1 − 2 + 2 and −3 + 1 + 2 + 2 all give 2. The two 2s are different elements, so the first two choices count separately.

Example 2

Input: nums = [0, 4, 0], target = -4

Output: 4

Explanation: The 4 must get a minus sign. Each 0 can take either sign without changing the sum, so there are 2 × 2 = 4 choices.

Example 3

Input: nums = [1, 2, 3], target = 8

Output: 0

Explanation: The largest possible sum is 1 + 2 + 3 = 6, so no choice reaches 8.

Check your understanding

Work out the answer for this input before you write any code.

nums = [1, 1, 1], target = 1

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 100
-10⁹ ≤ target ≤ 10⁹

Clarifying questions

What you would ask an interviewer before writing any code.