1150. Target Sum — Assign + / - Signs

Given an array nums and a target, assign a '+' or '-' sign to each element so the signed sum equals the target. Return the number of sign assignments that achieve it. The input is JSON {nums, target}.

Input: JSON {nums, target}.

Output: Integer — the number of valid assignments.

Examples

Input: {"nums":[1,1,1,1,1],"target":3}
Output: 5
Explanation: Five sign patterns give 3.

Input: {"nums":[1],"target":1}
Output: 1
Explanation: Assign +1.

Input: {"nums":[1,2,3],"target":0}
Output: 2
Explanation: Two assignments give 0.

Constraints

• 1<=n<=100

Asked by