792. Target Sum — Assign +/- to Each Number (Modulo 10^9+7)

Given an array of non-negative integers nums and an integer target, assign a '+' or '-' sign to each element and return the number of distinct assignments that make the expression evaluate to target, taken modulo 10^9 + 7. Implement with recursion + memoization.

Input: An array of non-negative integers and a target: "[a1,...], target".

Output: Return an integer count mod 10^9 + 7.

Examples

Input: [1,1,1,1,1], 3
Output: 5
Explanation: Five ways to assign +/- to get sum 3.

Input: [1], 1
Output: 1
Explanation: +1 = 1.

Input: [1], 2
Output: 0
Explanation: +1 = 1, -1 = -1; neither equals 2.

Constraints

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• -10000 <= target <= 10000

Asked by