Google面试题 | 目标和

题目描述

现有一个非负整数列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))