Target Sum in Java

You get an array nums and a number target.

Put a + or a - in front of each number, then add them all up. Return how many choices of signs give a total of target.

Two choices differ when some number gets another sign. So +0 and -0 count as two choices.

The count can get huge, so return it modulo 1,000,000,007.

Example 1:

Input: nums = [2,3,5], target = 0
Output: 2
Explanation: These two choices give 0:
+2 + 3 - 5 = 0
-2 - 3 + 5 = 0

Example 2:

Input: nums = [4,0,1], target = 3
Output: 2
Explanation: The 0 can take either sign:
+4 + 0 - 1 = 3
+4 - 0 - 1 = 3

Example 3:

Input: nums = [6,2], target = 5
Output: 0
Explanation: The four totals are 8, 4, -4 and -8.
None of them is 5.

Constraints:

• 1 to 100 numbers.
• Each number is a whole number from 0 to 1,000.
• The numbers add up to at most 1,000.
• target is a whole number from -1,000 to 1,000.