1355 - 目标和

给你一个整数数组 nums 和一个整数 target

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

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

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

输入

第一行为一个整数n,表示nums数组有n个元素

第二行为n个整数,表示n个数组元素

第三行为一个整数target,表示要求的运算结果

输出

符合要求的表达式的数目

样例

输入

5
1 1 1 1 1
3

输出

5

输入

1
1
1

输出

1

提示

  • 1 <= nums.length <= 20

  • 0 <= nums[i] <= 1000

  • 0 <= sum(nums[i]) <= 1000

  • -1000 <= target <= 1000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题