目标和

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

你需要从数组中选出一个子集，并为它们选择 +，其余元素选择 -，从而构造出一个表达式。返回构造该表达式的不同方法数目。

约定

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums) <= 1000
• -1000 <= target <= 1000
• 只要两个表达式中选择 + 的位置集合不同，就视为不同方法。

输入

• nums：非负整数数组
• target：目标和

输出

能使表达式结果等于 target 的不同方法数。

示例一

输入：

nums = [1, 1, 1, 1, 1], target = 3

输出：

5

解释：共有 5 种方式让结果为 3，例如 +1+1+1-1-1 = 3。

示例二

输入：

nums = [1], target = 1

输出：

1

复杂度要求

• 时间复杂度：O(n * sum)
• 空间复杂度：O(sum)