226 - 494 目标和

题目

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3 输出: 5 解释:

-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

一共有5种方法让最终目标和为3。

注意:

1. 数组非空，且长度不会超过20。

2. 初始的数组的和不会超过1000。

3. 保证返回的最终结果能被32位整数存下。

解答

https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/

原来的问题能转化成一个求子集和的问题：

找到一个全正数的子集，使得其和等于target+sum(nums)

就能转化成01背包问题了

dp代表组合成数字i，有多少种方法

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if sum(nums) < S or (sum(nums)+S) % 2 == 1:
            return 0
        P = (sum(nums)+S)//2
        dp = [1]+[0]*P
        for num in nums:
            for j in range(P, num-1, -1):
                dp[j] += dp[j-num]
        return dp[P]

Runtime: 72 ms, faster than 98.96% of Python3 online submissions for Target Sum.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Target Sum.