5798: 目标和

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

Input

输入一个非负整数数组nums 和 最后需要表达式计算的值target

Output

有几种方法可以让表达式的值等于target

Sample Input Copy 

1 1 1 1 1 
3

Sample Output Copy 

5

HINT

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

Source/Category

SubmitSubmit RecordStatisticsShowOff!