python - 元素可以为零时的目标求和dp算法

Question

目标总和提示:

You are given a set of positive numbers and a target sum ‘S’. Each number should be assigned either a ‘+’ or ‘-’ sign. We need to find the total ways to assign symbols to make the sum of the numbers equal to the target ‘S’.

Input: {1, 1, 2, 3}, S=1
Output: 3
Explanation: The given set has '3' ways to make a sum of '1': {+1-1-2+3} & {-1+1-2+3} & {+1+1+2-3}

假设“Sum(s1)”表示集合“s1”的总和，“Sum(s2)”表示集合“s2”的总和。添加负号以设置's2'

这个方程可以简化为子集求和问题target + sum(nums)/2

                  sum(s1) - sum(s2) = target
                  sum(s1) + sum(s2) = sum(nums)
                       2 * sum(s1) = target + sum(nums)
                           sum(s1) = target + sum(nums) / 2

def findTargetSumWays(nums, S):
    """
    :type nums: List[int]
    :type S: int
    :rtype: int
    """

    if (sum(nums) + S) % 2 == 1 or sum(nums) < S:
        return 0

    ssum = (sum(nums) + S) // 2

    dp = [[0 for _ in range(ssum + 1)] for _ in range(len(nums))]

    # col == 0
    for i in range(len(nums)):
        # [] or [0]
        if i == 0 and nums[i] == 0:
            dp[i][0] = 2
        # [] or [0] from previous
        elif nums[i] == 0:
            dp[i][0] = 2 * dp[i-1][0]
        else:  # empty set only
            dp[i][0] = 1

    # take 1st element nums[0] in s == nums[0]
    for s in range(1, ssum + 1):
        if nums[0] == s:
            dp[0][s] = 1

    for i in range(1, len(nums)):
        for s in range(1, ssum + 1):
            if nums[i] != 0:
                # skip element at i
                dp[i][s] = dp[i - 1][s]

                # include element at i
                if s >= nums[i]:
                    dp[i][s] += dp[i - 1][s - nums[i]]
            else: # nums[i] = 0

                dp[i][s] = dp[i-1][s] * 2

    return dp[len(nums) - 1][ssum]

我在这个提示上花了几个小时，但仍然无法通过下面的例子

[7,0,3,9,9,9,1,7,2,3]
6

expected: 50
output: 43 (using my algorithm)

我也看了别人的回答here ，它们都是有道理的，但我只想知道我在这里的算法中可能遗漏了什么地方？

Answer 1

你可以这样做:

from itertools import product

def findTargetSumWays(nums, S):
        a = [1,-1]
        result=[np.multiply(nums,i) for i in list(product(a, repeat=len(nums))) if sum(np.multiply(nums,i))==S]
        return(len(result))

findTargetSumWays(inputs,6)
50

基本上，我在与输入元素大小相同的元组中得到 -1,1 的所有可能组合，然后我将这些元组与输入相乘。