题目描述

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

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

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

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

输入格式

第一行两个空格隔开的整数 $n$ 和 $target$;

接下来一行 $n$ 个空格隔开的整数表示数组中的各个元素 $nums_i$。

输出格式

一行一个整数表示答案。

示例 1：

5 3
1 1 1 1 1

5

解释: 一共有 5 种方法让最终目标和为 3 。

-1 + 1 + 1 + 1 + 1 = 3

+1 - 1 + 1 + 1 + 1 = 3

+1 + 1 - 1 + 1 + 1 = 3

+1 + 1 + 1 - 1 + 1 = 3

+1 + 1 + 1 + 1 - 1 = 3

示例 2：

1 1
1

1

提示：

100%的数据满足以下条件。

• $1 <= n <= 50$
• $0 <= nums[i] <= 1000$
• $0 <= sum(nums[i]) <= 1000$
• $-1000 <= target <= 1000$

其中 $30\%$的数据， $1 \le n \le 20$。

SOURCE

目标和