题目描述
现有一个非负整数列a1, a2, ..., an和一个期望值S。你可以为每一个整数赋一个新符号，符号从+和-两种符号中选择。计算出有多少种组合可以令赋予符号后的这些整数的和等于S。
样例
输入：数列nums=[1,1,1,1,1]，S=3
输出：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
数据范围
1.数组长度为正数并不超过20
2.数组中所有整数的和不超过1000
3.输出的答案不会超过32位整数（2,147,483,647）
Python
def dp(n,S,nums):
if n == 1 :
if nums[0] == 0:
if S != 0 :
return 0
else:
return 2
else:
if S == nums[0] or S == 0 - nums[0]:
return 1
else:
return 0
else:
if S > sum(nums) or S < 0-sum(nums):
return 0
elif S == sum(nums) or S == 0-sum(nums):
return 1
else:
return dp(n-1,S-nums[-1],nums[:-1]) + dp(n-1,S+nums[-1],nums[:-1])
t = int(input())
for i in range(t):
n,S = list(map(int,input().split(' ')));
nums = list(map(int,input().split(' ')));
print(dp(n,S,nums))
