经典启蒙：子数和

---

image.png

递归暴力

看到题，二话不说直接递归，然后果断超时。

class Solution:
    def __init__(self):
        self.counts=0
    def helper(self,nums,target,start):
        if start ==len(nums):
            if target==0:
                self.counts+=1
            return
        self.helper(nums,target-nums[start],start+1)
        self.helper(nums,target+nums[start],start+1)
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.helper(nums,target,0)
        return self.counts

记事本 dp

target和start显然是变量，可以作为状态记录当前（target，start）对应的解的个数。

class Solution:
    def __init__(self):
        self.d={}
    def helper(self,nums,target,start):
        if start ==len(nums):
            if target==0:
                return 1
            return 0
        if (target,start) in self.d:
            return self.d[target,start]
        t1=self.helper(nums,target-nums[start],start+1)
        self.d[target-nums[start],start+1]=t1
        t2=self.helper(nums,target+nums[start],start+1)
        self.d[target+nums[start],start+1]=t2
        return t1+t2
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        return self.helper(nums,target,0)

背包dp

如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2

但是元素和可能无法整除2 或者 和小于数组所有元素和 = > 不存在解

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sums=sum(nums)
        if sums < target or (sums + target) % 2 == 1:
            return 0
        t=(target+sums)//2
        dp=[[0 for i in range(t+1)]for j in range(len(nums)+1)]
        dp[0][0]=1
        for i in range(1,len(nums)+1):
            for j in range(0,t+1):
                if (j<nums[i-1]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]]
        return dp[-1][t]