723. Plus or Minus
A street performer has a row of numbered cards, the values being listed in nums. Before the show, the performer writes either a plus or a minus sign in front of every card and then adds the signed values from left to right.
Return the number of different sign choices whose total equals target. Two choices differ if some card gets a different sign, so a card showing 0 can be signed in two distinct ways and both are counted. Because the count can be huge, return it modulo 1000000007. If no choice works, return 0.
Aim for time O(n * S) with S the sum of nums, and space O(S).
Example 1
- Input:
- nums = [3,1,4,1,5], target = -2
- Output:
- 3
- Explanation:
The total is 14, so the plus cards must sum to (14 - 2) / 2 = 6; that happens for the card sets {1, 5} (using either 1), and {1, 4, 1}, giving 3 sign patterns.
Example 2
- Input:
- nums = [2,0,2], target = 4
- Output:
- 2
- Explanation:
Both +2 +0 +2 and +2 -0 +2 reach 4, so the zero card gives two ways.
Constraints
1 ≤ nums.length ≤ 150
0 ≤ nums[i] ≤ 40
-6000 ≤ target ≤ 6000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n * S)
- Space
- O(S)