美文网首页
Google面试题 | 目标和

Google面试题 | 目标和

作者: data_x | 来源:发表于2017-05-27 11:36 被阅读11次

题目描述

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

相关文章

网友评论

      本文标题:Google面试题 | 目标和

      本文链接:https://www.haomeiwen.com/subject/ywxqfxtx.html